    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.commons.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            try
    281            {
    282                if (newSize == entries.length)
    283                {
    284                    // Time to expand!
    285
    286                    int newCapacity = (size * 3) / 2 + 1;
    287
    288                    CIMEntry<V>[] newEntries = new CIMEntry[newCapacity];
    289
    290                    System.arraycopy(entries, 0, newEntries, 0, cursor);
    291
    292                    System.arraycopy(entries, cursor, newEntries, cursor + 1, size - cursor);
    293
    294                    entries = newEntries;
    295                }
    296                else
    297                {
    298                    // Open up a space for the new entry
    299                    System.arraycopy(entries, cursor, entries, cursor + 1, size - cursor);
    300                }
    301            } catch (ArrayIndexOutOfBoundsException e)
    302            {
    303                // TAP5-2526
    304                throw new ConcurrentModificationException();
    305            }
    306
    307            CIMEntry<V> newEntry = new CIMEntry<V>(key, hashCode, newValue);
    308            entries[cursor] = newEntry;
    309
    310            size++;
    311
    312            // This is definitely a structural change
    313
    314            modCount++;
    315
    316            return null;
    317        }
    318
    319    }
    320
    321    // The list of entries. This is kept sorted by hash code. In some cases, there may be different
    322    // keys with the same hash code in adjacent indexes.
    323    private CIMEntry<V>[] entries;
    324
    325    private int size = 0;
    326
    327    // Used by iterators to check for concurrent modifications
    328
    329    private transient int modCount = 0;
    330
    331    private transient Set<Map.Entry<String, V>> entrySet;
    332
    333    public CaseInsensitiveMap()
    334    {
    335        this(DEFAULT_SIZE);
    336    }
    337
    338    @SuppressWarnings("unchecked")
    339    public CaseInsensitiveMap(int size)
    340    {
    341        entries = new CIMEntry[Math.max(size, 3)];
    342    }
    343
    344    public CaseInsensitiveMap(Map<String, ? extends V> map)
    345    {
    346        this(map.size());
    347
    348        for (Map.Entry<String, ? extends V> entry : map.entrySet())
    349        {
    350            put(entry.getKey(), entry.getValue());
    351        }
    352    }
    353
    354    @Override
    355    public void clear()
    356    {
    357        for (int i = 0; i < size; i++)
    358            entries[i] = null;
    359
    360        size = 0;
    361        modCount++;
    362    }
    363
    364    @Override
    365    public boolean isEmpty()
    366    {
    367        return size == 0;
    368    }
    369
    370    @Override
    371    public int size()
    372    {
    373        return size;
    374    }
    375
    376    @Override
    377    public V put(String key, V value)
    378    {
    379        int hashCode = caseInsenitiveHashCode(key);
    380
    381        return select(key, hashCode).put(key, hashCode, value);
    382    }
    383
    384    @Override
    385    public boolean containsKey(Object key)
    386    {
    387        return select(key).isFound();
    388    }
    389
    390    @Override
    391    public V get(Object key)
    392    {
    393        return select(key).get();
    394    }
    395
    396    @Override
    397    public V remove(Object key)
    398    {
    399        return select(key).remove();
    400    }
    401
    402    @Override
    403    public Set<Map.Entry<String, V>> entrySet()
    404    {
    405        if (entrySet == null) entrySet = new EntrySet();
    406
    407        return entrySet;
    408    }
    409
    410    @Override
    411    public Set<String> keySet() {
    412
    413        AbstractSet<String> set = new AbstractSet<String>() {
    414
    415          @Override
    416          public Iterator<String> iterator() {
    417
    418            final Iterator<java.util.Map.Entry<String, V>> entrySetIterator = entrySet().iterator();
    419
    420            return new Iterator<String>() {
    421              @Override
    422              public boolean hasNext() {
    423                return entrySetIterator.hasNext();
    424              }
    425              @Override
    426              public String next() {
    427                String nextKey = entrySetIterator.next().getKey();
    428                return nextKey;
    429              }
    430
    431              @Override
    432              public void remove() {
    433                throw new UnsupportedOperationException("Modifications to the key set are not allowed.");
    434              }
    435            };
    436          }
    437
    438          @Override
    439          public boolean contains(Object o) {
    440            return containsKey(o);
    441          }
    442
    443          @Override
    444          public int size() {
    445            return size;
    446          }
    447        };
    448
    449        return Collections.unmodifiableSet(set);
    450    }
    451
    452    private Position select(Object key)
    453    {
    454        if (key == null || key instanceof String)
    455        {
    456            String keyString = (String) key;
    457            return select(keyString, caseInsenitiveHashCode(keyString));
    458        }
    459
    460        return new Position(0, false);
    461    }
    462
    463    /**
    464     * Searches the elements for the index of the indicated key and (case insensitive) hash code. Sets the _cursor and
    465     * _found attributes.
    466     */
    467    private Position select(String key, int hashCode)
    468    {
    469        if (size == 0) return new Position(0, false);
    470
    471        int low = 0;
    472        int high = size - 1;
    473
    474        int cursor;
    475
    476        try
    477        {
    478            while (low <= high)
    479            {
    480                cursor = (low + high) >> 1;
    481
    482                CIMEntry<V> e = entries[cursor];
    483
    484                if (e == null)
    485                {
    486                    // TAP5-2520
    487                    throw new ConcurrentModificationException();
    488                }
    489
    490                if (e.hashCode < hashCode)
    491                {
    492                    low = cursor + 1;
    493                    continue;
    494                }
    495
    496                if (e.hashCode > hashCode)
    497                {
    498                    high = cursor - 1;
    499                    continue;
    500                }
    501
    502                return tunePosition(key, hashCode, cursor);
    503            }
    504        } catch (ArrayIndexOutOfBoundsException e)
    505        {
    506            // TAP5-2526
    507            throw new ConcurrentModificationException();
    508        }
    509
    510        return new Position(low, false);
    511    }
    512
    513    /**
    514     * select() has located a matching hashCode, but there's an outlying possibility that multiple keys share the same
    515     * hashCode. Backup the cursor until we get to locate the initial hashCode match, then march forward until the key
    516     * is located, or the hashCode stops matching.
    517     *
    518     * @param key
    519     * @param hashCode
    520     */
    521    private Position tunePosition(String key, int hashCode, int cursor)
    522    {
    523        boolean found = false;
    524
    525        while (cursor > 0)
    526        {
    527            if (entries[cursor - 1].hashCode != hashCode) break;
    528
    529            cursor--;
    530        }
    531
    532        while (true)
    533        {
    534            if (entries[cursor].matches(key))
    535            {
    536                found = true;
    537                break;
    538            }
    539
    540            // Advance to the next entry.
    541
    542            cursor++;
    543
    544            // If out of entries,
    545            if (cursor >= size || entries[cursor].hashCode != hashCode) break;
    546        }
    547
    548        return new Position(cursor, found);
    549    }
    550
    551    static int caseInsenitiveHashCode(String input)
    552    {
    553        if (input == null) return NULL_HASH;
    554
    555        int length = input.length();
    556        int hash = 0;
    557
    558        // This should end up more or less equal to input.toLowerCase().hashCode(), unless String
    559        // changes its implementation. Let's hope this is reasonably fast.
    560
    561        for (int i = 0; i < length; i++)
    562        {
    563            int ch = input.charAt(i);
    564
    565            int caselessCh = Character.toLowerCase(ch);
    566
    567            hash = 31 * hash + caselessCh;
    568        }
    569
    570        return hash;
    571    }
    572
    573}