1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 package info.rolandkrueger.roklib.util;
26
27 import info.rolandkrueger.roklib.util.helper.CheckForNull;
28
29 import java.io.Serializable;
30 import java.util.AbstractMap;
31 import java.util.AbstractMap.SimpleEntry;
32 import java.util.AbstractSet;
33 import java.util.ArrayList;
34 import java.util.Collection;
35 import java.util.Comparator;
36 import java.util.Iterator;
37 import java.util.LinkedList;
38 import java.util.List;
39 import java.util.Locale;
40 import java.util.Map;
41 import java.util.Set;
42 import java.util.SortedMap;
43 import java.util.SortedSet;
44 import java.util.TreeSet;
45
46 public class TernarySearchTreeMapCaseInsensitive<V> implements ITernarySearchTreeMap<V>
47 {
48 private static final long serialVersionUID = 6106815305526987949L;
49
50 private TernarySearchTreeMap<Map.Entry<CharSequence, V>> mData;
51 private Locale mLocale;
52
53 public TernarySearchTreeMapCaseInsensitive ()
54 {
55 this (null);
56 }
57
58 public TernarySearchTreeMapCaseInsensitive (Locale pLocale)
59 {
60 mLocale = pLocale;
61 if (mLocale == null)
62 {
63 mLocale = Locale.getDefault ();
64 }
65 mData = new TernarySearchTreeMap<Map.Entry<CharSequence,V>> ();
66 }
67
68 public SortedSet<CharSequence> matchAlmost (CharSequence key, int distance, int lengthTolerance)
69 {
70 CheckForNull.check (key);
71 SortedSet<CharSequence> result = new TreeSet<CharSequence> ();
72 for (CharSequence resultKey : mData.matchAlmost (key.toString ().toLowerCase (mLocale), distance, lengthTolerance))
73 {
74 result.add (mData.get (resultKey).getKey ());
75 }
76 return result;
77 }
78
79 public Entry<CharSequence, V> getEntry (Object key)
80 {
81 String keyString = ((CharSequence) key).toString ().toLowerCase (mLocale);
82 Entry<CharSequence, Map.Entry<CharSequence, V>> entry = mData.getEntry (keyString);
83 return entry == null ? null :
84 new AbstractMap.SimpleEntry<CharSequence, V> (entry.getValue ().getKey (), entry.getValue ().getValue ());
85 }
86
87 public V getValueAt (int index)
88 {
89 return mData.getValueAt (index).getValue ();
90 }
91
92 public CharSequence getKeyAt (int index)
93 {
94 return mData.get (mData.getKeyAt (index)).getKey ();
95 }
96
97 public int indexOf (CharSequence key)
98 {
99 return mData.indexOf (key.toString ().toLowerCase (mLocale));
100 }
101
102 public Iterable<CharSequence> getKeysForPrefix (CharSequence prefix)
103 {
104 CheckForNull.check (prefix);
105 final Iterator<Entry<CharSequence, Map.Entry<CharSequence, V>>> iterator =
106 mData.getPrefixSubtreeIterator (prefix.toString ().toLowerCase (mLocale), false);
107
108 return new Iterable<CharSequence>()
109 {
110 public Iterator<CharSequence> iterator ()
111 {
112 return new Iterator<CharSequence> () {
113
114 public boolean hasNext ()
115 {
116 return iterator.hasNext ();
117 }
118
119 public CharSequence next ()
120 {
121 return iterator.next ().getValue ().getKey ();
122 }
123
124 public void remove ()
125 {
126 iterator.remove ();
127 }};
128 }
129 };
130 }
131
132 public Iterator<Entry<CharSequence, V>> getPrefixSubtreeIterator (String prefix)
133 {
134 return getPrefixSubtreeIterator (prefix, false);
135 }
136
137 public Iterator<Entry<CharSequence, V>> getPrefixSubtreeIterator (String pPrefix,
138 boolean inverseSearch)
139 {
140 CheckForNull.check (pPrefix);
141 final Iterator<Entry<CharSequence, Map.Entry<CharSequence, V>>> iterator =
142 mData.getPrefixSubtreeIterator (pPrefix.toLowerCase (mLocale), inverseSearch);
143
144 return new Iterator<Map.Entry<CharSequence, V>> () {
145
146 public boolean hasNext ()
147 {
148 return iterator.hasNext ();
149 }
150
151 public java.util.Map.Entry<CharSequence, V> next ()
152 {
153 return iterator.next ().getValue ();
154 }
155
156 public void remove ()
157 {
158 iterator.remove ();
159 }};
160 }
161
162 public Entry<CharSequence, V> predecessor (Object keyObject)
163 {
164 Map.Entry<CharSequence, Map.Entry<CharSequence, V>> entry = mData.predecessor (((CharSequence) keyObject).toString ().toLowerCase (mLocale));
165 return entry == null ? null : entry.getValue ();
166 }
167
168 public Entry<CharSequence, V> successor (Object keyObject)
169 {
170 Map.Entry<CharSequence, Map.Entry<CharSequence, V>> entry = mData.successor (((CharSequence) keyObject).toString ().toLowerCase (mLocale));
171 return entry == null ? null : entry.getValue ();
172 }
173
174 public int size ()
175 {
176 return mData.size ();
177 }
178
179 public boolean isEmpty ()
180 {
181 return mData.isEmpty ();
182 }
183
184 @Override
185 public String toString ()
186 {
187 return entrySet ().toString ();
188 }
189
190 public boolean containsKey (Object key)
191 {
192 return mData.containsKey (key.toString ().toLowerCase (mLocale));
193 }
194
195 public boolean containsValue (Object pValue)
196 {
197 for (Map.Entry<CharSequence, V> entry : mData.values ())
198 {
199 if (entry.getValue ().equals (pValue)) return true;
200 }
201 return false;
202 }
203
204 public V get (Object key)
205 {
206 String keyString = ((CharSequence) key).toString ().toLowerCase (mLocale);
207 Map.Entry<CharSequence, V> result = mData.get (keyString);
208 return result == null ? null : result.getValue ();
209 }
210
211 public V put (CharSequence key, V value)
212 {
213 CheckForNull.check (key, value);
214 SimpleEntry<CharSequence, V> entry = new SimpleEntry<CharSequence, V> (key, value);
215 Map.Entry<CharSequence, V> oldValue = mData.put (key.toString ().toLowerCase (mLocale), entry);
216 return oldValue == null ? null : oldValue.getValue ();
217 }
218
219 public V remove (Object key)
220 {
221 String keyString = ((CharSequence) key).toString ().toLowerCase (mLocale);
222 Map.Entry<CharSequence, V> entry = mData.remove (keyString);
223 return entry == null ? null : entry.getValue ();
224 }
225
226 public void putAll (Map<? extends CharSequence, ? extends V> map)
227 {
228 for (Map.Entry<? extends CharSequence, ? extends V> entry : map.entrySet ())
229 {
230 put (entry.getKey (), entry.getValue ());
231 }
232 }
233
234 public void clear ()
235 {
236 mData.clear ();
237 }
238
239 public Comparator<? super CharSequence> comparator ()
240 {
241 return mData.comparator ();
242 }
243
244 public SortedMap<CharSequence, V> subMap (CharSequence fromKey, CharSequence toKey)
245 {
246 return new TSTSubMapCaseInsensitive (fromKey, toKey);
247 }
248
249 public SortedMap<CharSequence, V> headMap (CharSequence toKey)
250 {
251 return new TSTSubMapCaseInsensitive (null, toKey);
252 }
253
254 public SortedMap<CharSequence, V> tailMap (CharSequence fromKey)
255 {
256 return new TSTSubMapCaseInsensitive (fromKey, null);
257 }
258
259 public CharSequence firstKey ()
260 {
261 if (mData.isEmpty ()) return null;
262 return mData.get (mData.firstKey ()).getKey ();
263 }
264
265 public CharSequence lastKey ()
266 {
267 if (mData.isEmpty ()) return null;
268 return mData.get (mData.lastKey ()).getKey ();
269 }
270
271 public Set<CharSequence> keySet ()
272 {
273 return new TSTKeySetCaseInsensitive ();
274 }
275
276 public Collection<V> values ()
277 {
278 Collection<Map.Entry<CharSequence, V>> mapValues = mData.values ();
279 List<V> result = new ArrayList<V> (mapValues.size ());
280 for (Map.Entry<CharSequence, V> entry : mapValues)
281 {
282 result.add (entry.getValue ());
283 }
284 return result;
285 }
286
287 public Set<Map.Entry<CharSequence, V>> entrySet ()
288 {
289 return new TSTEntrySetCaseInsensitive (null, null);
290 }
291
292 private class TSTEntrySetCaseInsensitive extends AbstractSet<Entry<CharSequence, V>> implements Serializable
293 {
294 private static final long serialVersionUID = - 291147638123041581L;
295 private Set<Map.Entry<CharSequence, Map.Entry<CharSequence, V>>> mEntrySet;
296
297 public TSTEntrySetCaseInsensitive (CharSequence fromKey, CharSequence toKey)
298 {
299 if (fromKey != null && toKey != null)
300 {
301 mEntrySet = mData.subMap (fromKey.toString ().toLowerCase (mLocale), toKey.toString ().toLowerCase (mLocale)).entrySet ();
302 } else if (fromKey != null && toKey == null)
303 {
304 mEntrySet = mData.tailMap (fromKey.toString ().toLowerCase (mLocale)).entrySet ();
305 } else if (fromKey == null && toKey != null)
306 {
307 mEntrySet = mData.headMap (toKey.toString ().toLowerCase (mLocale)).entrySet ();
308 } else
309 {
310 mEntrySet = mData.entrySet ();
311 }
312 }
313
314 @Override
315 public Iterator<Map.Entry<CharSequence, V>> iterator ()
316 {
317 final Iterator<Entry<CharSequence, Map.Entry<CharSequence, V>>> entryIterator = mEntrySet.iterator ();
318
319 return new Iterator<Map.Entry<CharSequence, V>> () {
320
321 public boolean hasNext ()
322 {
323 return entryIterator.hasNext ();
324 }
325
326 public java.util.Map.Entry<CharSequence, V> next ()
327 {
328 return entryIterator.next ().getValue ();
329 }
330
331 public void remove ()
332 {
333 entryIterator.remove ();
334 }};
335 }
336
337 @Override
338 public int size ()
339 {
340 return mEntrySet.size ();
341 }
342
343 @Override
344 public boolean isEmpty ()
345 {
346 return mEntrySet.isEmpty ();
347 }
348
349 @Override
350 @SuppressWarnings ({ "rawtypes", "unchecked" })
351 public boolean contains (Object object)
352 {
353 if (! (object instanceof Map.Entry)) return false;
354 Map.Entry entry = (Map.Entry) object;
355 if (entry.getKey () == null) return false;
356 String lowerCaseKey = entry.getKey ().toString ().toLowerCase (mLocale);
357 Map.Entry value = mData.get (lowerCaseKey);
358 if (value == null) return false;
359 return mEntrySet.contains (new SimpleEntry<CharSequence, Map.Entry<CharSequence, V>> (lowerCaseKey,
360 new SimpleEntry (value.getKey (), entry.getValue ())));
361 }
362
363 @Override
364 public boolean add (Map.Entry<CharSequence, V> e)
365 {
366 throw new UnsupportedOperationException (new String ("TernarySearchTreeMapCaseInsensitive's entry set: add() not allowed!"));
367 }
368
369 @Override
370 @SuppressWarnings ({ "rawtypes", "unchecked" })
371 public boolean remove (Object object)
372 {
373 if (! (object instanceof Map.Entry)) return false;
374 Map.Entry entry = (Map.Entry) object;
375 if (entry.getKey () == null) return false;
376 String lowerCaseKey = entry.getKey ().toString ().toLowerCase (mLocale);
377 Map.Entry value = mData.get (lowerCaseKey);
378 if (value == null) return false;
379 return mEntrySet.remove (new SimpleEntry<CharSequence, Map.Entry<CharSequence, V>> (lowerCaseKey,
380 new SimpleEntry (value.getKey (), entry.getValue ())));
381 }
382
383 @Override
384 public boolean retainAll (Collection<?> collection)
385 {
386 return super.retainAll (getEntriesFromMap (collection));
387 }
388
389 @SuppressWarnings ({ "rawtypes", "unchecked" })
390 private Collection<?> getEntriesFromMap (Collection<?> collection)
391 {
392 List list = new LinkedList ();
393 for (Object obj : collection)
394 {
395 if (! (obj instanceof Map.Entry)) continue;
396 Map.Entry entry = (Map.Entry) obj;
397 Map.Entry mapEntry = getEntry (entry.getKey ());
398 if (mapEntry != null) list.add (mapEntry);
399 }
400 return list;
401 }
402
403 @Override
404 public boolean removeAll (Collection<?> collection)
405 {
406 return super.removeAll (getEntriesFromMap (collection));
407 }
408
409 @Override
410 public boolean addAll (Collection<? extends Map.Entry<CharSequence, V>> c)
411 {
412 throw new UnsupportedOperationException (new String ("TernarySearchTreeMapCaseInsensitive's entry set: addAll() not allowed!"));
413 }
414
415 @Override
416 public void clear ()
417 {
418 mEntrySet.clear ();
419 }
420 }
421
422 private class TSTSubMapCaseInsensitive extends AbstractMap<CharSequence, V> implements SortedMap<CharSequence, V>, Serializable
423 {
424 private static final long serialVersionUID = 6887075934244545880L;
425
426 private SortedMap<CharSequence, Map.Entry<CharSequence, V>> mSubMap;
427 private CharSequence mFromKey;
428 private CharSequence mExclusiveToKey;
429
430 public TSTSubMapCaseInsensitive () {}
431
432 public TSTSubMapCaseInsensitive (CharSequence fromKey, CharSequence toKey)
433 {
434 mFromKey = fromKey;
435 mExclusiveToKey = toKey;
436 if (fromKey == null && toKey != null)
437 {
438 mSubMap = mData.headMap (toKey.toString ().toLowerCase (mLocale));
439 } else if (toKey == null && fromKey != null)
440 {
441 mSubMap = mData.tailMap (fromKey.toString ().toLowerCase (mLocale));
442 } else if (fromKey != null && toKey != null)
443 {
444 mSubMap = mData.subMap (fromKey.toString ().toLowerCase (mLocale), toKey.toString ().toLowerCase (mLocale));
445 } else
446 {
447 throw new IllegalArgumentException ("fromKey is null and toKey is null");
448 }
449 }
450
451 public Comparator<? super CharSequence> comparator ()
452 {
453
454 return null;
455 }
456
457 public V put(CharSequence key, V value)
458 {
459 CheckForNull.check (key, value);
460 SimpleEntry<CharSequence, V> entry = new SimpleEntry<CharSequence, V> (key, value);
461 Map.Entry<CharSequence, V> oldValue = mSubMap.put (key.toString ().toLowerCase (mLocale), entry);
462 return oldValue == null ? null : oldValue.getValue ();
463 }
464
465 @Override
466 public boolean containsKey (Object key)
467 {
468 if (key == null) return false;
469 if (! (key instanceof CharSequence)) return false;
470 return mSubMap.containsKey (key.toString ().toLowerCase (mLocale));
471 }
472
473 public SortedMap<CharSequence, V> subMap (CharSequence fromKey, CharSequence toKey)
474 {
475 TSTSubMapCaseInsensitive result = new TSTSubMapCaseInsensitive ();
476 result.mSubMap = mSubMap.subMap (fromKey.toString ().toLowerCase (mLocale), toKey.toString ().toLowerCase (mLocale));
477 return result;
478 }
479
480 public SortedMap<CharSequence, V> headMap (CharSequence toKey)
481 {
482 TSTSubMapCaseInsensitive result = new TSTSubMapCaseInsensitive ();
483 result.mSubMap = mSubMap.headMap (toKey.toString ().toLowerCase (mLocale));
484 return result;
485 }
486
487 public SortedMap<CharSequence, V> tailMap (CharSequence fromKey)
488 {
489 TSTSubMapCaseInsensitive result = new TSTSubMapCaseInsensitive ();
490 result.mSubMap = mSubMap.tailMap (fromKey.toString ().toLowerCase (mLocale));
491 return result;
492 }
493
494 public CharSequence firstKey ()
495 {
496 CharSequence firstKey = mSubMap.firstKey ();
497 return firstKey == null ? null : mSubMap.get (firstKey).getKey ();
498 }
499
500 public CharSequence lastKey ()
501 {
502 CharSequence lastKey = mSubMap.lastKey ();
503 return lastKey == null ? null : mSubMap.get (lastKey).getKey ();
504 }
505
506 @Override
507 public Set<Entry<CharSequence, V>> entrySet ()
508 {
509 return new TSTEntrySetCaseInsensitive (mFromKey, mExclusiveToKey);
510 }
511 }
512
513 private class TSTKeySetCaseInsensitive extends TernarySearchTreeMap<Map.Entry<CharSequence, V>>.TSTKeySet
514 {
515 private static final long serialVersionUID = - 4830094843193803479L;
516
517 private CharSequence mFromKey;
518 private CharSequence mExclusiveToKey;
519
520 public TSTKeySetCaseInsensitive ()
521 {
522 mData.super ();
523 }
524
525 public TSTKeySetCaseInsensitive (CharSequence fromKey, CharSequence toKey)
526 {
527 mData.super (fromKey, toKey);
528 mFromKey = fromKey;
529 mExclusiveToKey = toKey;
530 }
531
532 @Override
533 public boolean contains (Object o)
534 {
535 return super.contains (((CharSequence) o).toString ().toLowerCase (mLocale));
536 }
537
538 @Override
539 public boolean remove (Object o)
540 {
541 return super.remove (((CharSequence) o).toString ().toLowerCase (mLocale));
542 }
543
544 @Override
545 public Iterator<CharSequence> iterator ()
546 {
547 final Iterator<Entry<CharSequence, Map.Entry<CharSequence, V>>> entryIterator;
548 if (mFromKey != null || mExclusiveToKey != null)
549 {
550 entryIterator = mData.subMap (mFromKey, mExclusiveToKey).entrySet ().iterator ();
551 } else
552 {
553 entryIterator = mData.entrySet ().iterator ();
554 }
555
556 return new Iterator<CharSequence> ()
557 {
558 public boolean hasNext ()
559 {
560 return entryIterator.hasNext ();
561 }
562
563 public CharSequence next ()
564 {
565 return entryIterator.next ().getValue ().getKey ();
566 }
567
568 public void remove ()
569 {
570 entryIterator.remove ();
571 }
572 };
573 }
574 }
575 }