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