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