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}