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}