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
015 package org.apache.tapestry5.ioc.util;
016
017 import java.io.Serializable;
018 import 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 */
030 public 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 }