1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package org.mortbay.util;
16
17 import java.io.Externalizable;
18 import java.util.AbstractMap;
19 import java.util.Collections;
20 import java.util.HashMap;
21 import java.util.HashSet;
22 import java.util.Map;
23 import java.util.Set;
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 public class StringMap extends AbstractMap implements Externalizable
40 {
41 public static final boolean CASE_INSENSTIVE=true;
42 protected static final int __HASH_WIDTH=17;
43
44
45 protected int _width=__HASH_WIDTH;
46 protected Node _root=new Node();
47 protected boolean _ignoreCase=false;
48 protected NullEntry _nullEntry=null;
49 protected Object _nullValue=null;
50 protected HashSet _entrySet=new HashSet(3);
51 protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet);
52
53
54
55
56 public StringMap()
57 {}
58
59
60
61
62
63 public StringMap(boolean ignoreCase)
64 {
65 this();
66 _ignoreCase=ignoreCase;
67 }
68
69
70
71
72
73
74
75 public StringMap(boolean ignoreCase,int width)
76 {
77 this();
78 _ignoreCase=ignoreCase;
79 _width=width;
80 }
81
82
83
84
85
86 public void setIgnoreCase(boolean ic)
87 {
88 if (_root._children!=null)
89 throw new IllegalStateException("Must be set before first put");
90 _ignoreCase=ic;
91 }
92
93
94 public boolean isIgnoreCase()
95 {
96 return _ignoreCase;
97 }
98
99
100
101
102
103
104 public void setWidth(int width)
105 {
106 _width=width;
107 }
108
109
110 public int getWidth()
111 {
112 return _width;
113 }
114
115
116 public Object put(Object key, Object value)
117 {
118 if (key==null)
119 return put(null,value);
120 return put(key.toString(),value);
121 }
122
123
124 public Object put(String key, Object value)
125 {
126 if (key==null)
127 {
128 Object oldValue=_nullValue;
129 _nullValue=value;
130 if (_nullEntry==null)
131 {
132 _nullEntry=new NullEntry();
133 _entrySet.add(_nullEntry);
134 }
135 return oldValue;
136 }
137
138 Node node = _root;
139 int ni=-1;
140 Node prev = null;
141 Node parent = null;
142
143
144 charLoop:
145 for (int i=0;i<key.length();i++)
146 {
147 char c=key.charAt(i);
148
149
150 if (ni==-1)
151 {
152 parent=node;
153 prev=null;
154 ni=0;
155 node=(node._children==null)?null:node._children[c%_width];
156 }
157
158
159 while (node!=null)
160 {
161
162 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
163 {
164 prev=null;
165 ni++;
166 if (ni==node._char.length)
167 ni=-1;
168 continue charLoop;
169 }
170
171
172
173 if (ni==0)
174 {
175
176 prev=node;
177 node=node._next;
178 }
179 else
180 {
181
182 node.split(this,ni);
183 i--;
184 ni=-1;
185 continue charLoop;
186 }
187 }
188
189
190 node = new Node(_ignoreCase,key,i);
191
192 if (prev!=null)
193 prev._next=node;
194 else if (parent!=null)
195 {
196 if (parent._children==null)
197 parent._children=new Node[_width];
198 parent._children[c%_width]=node;
199 int oi=node._ochar[0]%_width;
200 if (node._ochar!=null && node._char[0]%_width!=oi)
201 {
202 if (parent._children[oi]==null)
203 parent._children[oi]=node;
204 else
205 {
206 Node n=parent._children[oi];
207 while(n._next!=null)
208 n=n._next;
209 n._next=node;
210 }
211 }
212 }
213 else
214 _root=node;
215 break;
216 }
217
218
219 if (node!=null)
220 {
221
222 if(ni>0)
223 node.split(this,ni);
224
225 Object old = node._value;
226 node._key=key;
227 node._value=value;
228 _entrySet.add(node);
229 return old;
230 }
231 return null;
232 }
233
234
235 public Object get(Object key)
236 {
237 if (key==null)
238 return _nullValue;
239 if (key instanceof String)
240 return get((String)key);
241 return get(key.toString());
242 }
243
244
245 public Object get(String key)
246 {
247 if (key==null)
248 return _nullValue;
249
250 Map.Entry entry = getEntry(key,0,key.length());
251 if (entry==null)
252 return null;
253 return entry.getValue();
254 }
255
256
257
258
259
260
261
262
263
264 public Map.Entry getEntry(String key,int offset, int length)
265 {
266 if (key==null)
267 return _nullEntry;
268
269 Node node = _root;
270 int ni=-1;
271
272
273 charLoop:
274 for (int i=0;i<length;i++)
275 {
276 char c=key.charAt(offset+i);
277
278
279 if (ni==-1)
280 {
281 ni=0;
282 node=(node._children==null)?null:node._children[c%_width];
283 }
284
285
286 while (node!=null)
287 {
288
289 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
290 {
291 ni++;
292 if (ni==node._char.length)
293 ni=-1;
294 continue charLoop;
295 }
296
297
298 if (ni>0) return null;
299
300
301 node=node._next;
302 }
303 return null;
304 }
305
306 if (ni>0) return null;
307 if (node!=null && node._key==null)
308 return null;
309 return node;
310 }
311
312
313
314
315
316
317
318
319
320 public Map.Entry getEntry(char[] key,int offset, int length)
321 {
322 if (key==null)
323 return _nullEntry;
324
325 Node node = _root;
326 int ni=-1;
327
328
329 charLoop:
330 for (int i=0;i<length;i++)
331 {
332 char c=key[offset+i];
333
334
335 if (ni==-1)
336 {
337 ni=0;
338 node=(node._children==null)?null:node._children[c%_width];
339 }
340
341
342 while (node!=null)
343 {
344
345 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
346 {
347 ni++;
348 if (ni==node._char.length)
349 ni=-1;
350 continue charLoop;
351 }
352
353
354 if (ni>0) return null;
355
356
357 node=node._next;
358 }
359 return null;
360 }
361
362 if (ni>0) return null;
363 if (node!=null && node._key==null)
364 return null;
365 return node;
366 }
367
368
369
370
371
372
373
374
375
376
377 public Map.Entry getBestEntry(byte[] key,int offset, int maxLength)
378 {
379 if (key==null)
380 return _nullEntry;
381
382 Node node = _root;
383 int ni=-1;
384
385
386 charLoop:
387 for (int i=0;i<maxLength;i++)
388 {
389 char c=(char)key[offset+i];
390
391
392 if (ni==-1)
393 {
394 ni=0;
395
396 Node child = (node._children==null)?null:node._children[c%_width];
397
398 if (child==null && i>0)
399 return node;
400 node=child;
401 }
402
403
404 while (node!=null)
405 {
406
407 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
408 {
409 ni++;
410 if (ni==node._char.length)
411 ni=-1;
412 continue charLoop;
413 }
414
415
416 if (ni>0) return null;
417
418
419 node=node._next;
420 }
421 return null;
422 }
423
424 if (ni>0) return null;
425 if (node!=null && node._key==null)
426 return null;
427 return node;
428 }
429
430
431
432 public Object remove(Object key)
433 {
434 if (key==null)
435 return remove(null);
436 return remove(key.toString());
437 }
438
439
440 public Object remove(String key)
441 {
442 if (key==null)
443 {
444 Object oldValue=_nullValue;
445 if (_nullEntry!=null)
446 {
447 _entrySet.remove(_nullEntry);
448 _nullEntry=null;
449 _nullValue=null;
450 }
451 return oldValue;
452 }
453
454 Node node = _root;
455 int ni=-1;
456
457
458 charLoop:
459 for (int i=0;i<key.length();i++)
460 {
461 char c=key.charAt(i);
462
463
464 if (ni==-1)
465 {
466 ni=0;
467 node=(node._children==null)?null:node._children[c%_width];
468 }
469
470
471 while (node!=null)
472 {
473
474 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
475 {
476 ni++;
477 if (ni==node._char.length)
478 ni=-1;
479 continue charLoop;
480 }
481
482
483 if (ni>0) return null;
484
485
486 node=node._next;
487 }
488 return null;
489 }
490
491 if (ni>0) return null;
492 if (node!=null && node._key==null)
493 return null;
494
495 Object old = node._value;
496 _entrySet.remove(node);
497 node._value=null;
498 node._key=null;
499
500 return old;
501 }
502
503
504 public Set entrySet()
505 {
506 return _umEntrySet;
507 }
508
509
510 public int size()
511 {
512 return _entrySet.size();
513 }
514
515
516 public boolean isEmpty()
517 {
518 return _entrySet.isEmpty();
519 }
520
521
522 public boolean containsKey(Object key)
523 {
524 if (key==null)
525 return _nullEntry!=null;
526 return
527 getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
528 }
529
530
531 public void clear()
532 {
533 _root=new Node();
534 _nullEntry=null;
535 _nullValue=null;
536 _entrySet.clear();
537 }
538
539
540
541
542
543 private static class Node implements Map.Entry
544 {
545 char[] _char;
546 char[] _ochar;
547 Node _next;
548 Node[] _children;
549 String _key;
550 Object _value;
551
552 Node(){}
553
554 Node(boolean ignoreCase,String s, int offset)
555 {
556 int l=s.length()-offset;
557 _char=new char[l];
558 _ochar=new char[l];
559 for (int i=0;i<l;i++)
560 {
561 char c=s.charAt(offset+i);
562 _char[i]=c;
563 if (ignoreCase)
564 {
565 char o=c;
566 if (Character.isUpperCase(c))
567 o=Character.toLowerCase(c);
568 else if (Character.isLowerCase(c))
569 o=Character.toUpperCase(c);
570 _ochar[i]=o;
571 }
572 }
573 }
574
575 Node split(StringMap map,int offset)
576 {
577 Node split = new Node();
578 int sl=_char.length-offset;
579
580 char[] tmp=this._char;
581 this._char=new char[offset];
582 split._char = new char[sl];
583 System.arraycopy(tmp,0,this._char,0,offset);
584 System.arraycopy(tmp,offset,split._char,0,sl);
585
586 if (this._ochar!=null)
587 {
588 tmp=this._ochar;
589 this._ochar=new char[offset];
590 split._ochar = new char[sl];
591 System.arraycopy(tmp,0,this._ochar,0,offset);
592 System.arraycopy(tmp,offset,split._ochar,0,sl);
593 }
594
595 split._key=this._key;
596 split._value=this._value;
597 this._key=null;
598 this._value=null;
599 if (map._entrySet.remove(this))
600 map._entrySet.add(split);
601
602 split._children=this._children;
603 this._children=new Node[map._width];
604 this._children[split._char[0]%map._width]=split;
605 if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
606 this._children[split._ochar[0]%map._width]=split;
607
608 return split;
609 }
610
611 public Object getKey(){return _key;}
612 public Object getValue(){return _value;}
613 public Object setValue(Object o){Object old=_value;_value=o;return old;}
614 public String toString()
615 {
616 StringBuffer buf=new StringBuffer();
617 synchronized(buf)
618 {
619 toString(buf);
620 }
621 return buf.toString();
622 }
623
624 private void toString(StringBuffer buf)
625 {
626 buf.append("{[");
627 if (_char==null)
628 buf.append('-');
629 else
630 for (int i=0;i<_char.length;i++)
631 buf.append(_char[i]);
632 buf.append(':');
633 buf.append(_key);
634 buf.append('=');
635 buf.append(_value);
636 buf.append(']');
637 if (_children!=null)
638 {
639 for (int i=0;i<_children.length;i++)
640 {
641 buf.append('|');
642 if (_children[i]!=null)
643 _children[i].toString(buf);
644 else
645 buf.append("-");
646 }
647 }
648 buf.append('}');
649 if (_next!=null)
650 {
651 buf.append(",\n");
652 _next.toString(buf);
653 }
654 }
655 }
656
657
658
659 private class NullEntry implements Map.Entry
660 {
661 public Object getKey(){return null;}
662 public Object getValue(){return _nullValue;}
663 public Object setValue(Object o)
664 {Object old=_nullValue;_nullValue=o;return old;}
665 public String toString(){return "[:null="+_nullValue+"]";}
666 }
667
668
669 public void writeExternal(java.io.ObjectOutput out)
670 throws java.io.IOException
671 {
672 HashMap map = new HashMap(this);
673 out.writeBoolean(_ignoreCase);
674 out.writeObject(map);
675 }
676
677
678 public void readExternal(java.io.ObjectInput in)
679 throws java.io.IOException, ClassNotFoundException
680 {
681 boolean ic=in.readBoolean();
682 HashMap map = (HashMap)in.readObject();
683 setIgnoreCase(ic);
684 this.putAll(map);
685 }
686 }