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            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}