View Javadoc

1   // ========================================================================
2   // Copyright 2004-2005 Mort Bay Consulting Pty. Ltd.
3   // ------------------------------------------------------------------------
4   // Licensed under the Apache License, Version 2.0 (the "License");
5   // you may not use this file except in compliance with the License.
6   // You may obtain a copy of the License at 
7   // http://www.apache.org/licenses/LICENSE-2.0
8   // Unless required by applicable law or agreed to in writing, software
9   // distributed under the License is distributed on an "AS IS" BASIS,
10  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11  // See the License for the specific language governing permissions and
12  // limitations under the License.
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  /** Map implementation Optimized for Strings keys..
27   * This String Map has been optimized for mapping small sets of
28   * Strings where the most frequently accessed Strings have been put to
29   * the map first.
30   *
31   * It also has the benefit that it can look up entries by substring or
32   * sections of char and byte arrays.  This can prevent many String
33   * objects from being created just to look up in the map.
34   *
35   * This map is NOT synchronized.
36   *
37   * @author Greg Wilkins (gregw)
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      /** Constructor. 
55       */
56      public StringMap()
57      {}
58      
59      /* ------------------------------------------------------------ */
60      /** Constructor. 
61       * @param ignoreCase 
62       */
63      public StringMap(boolean ignoreCase)
64      {
65          this();
66          _ignoreCase=ignoreCase;
67      }
68      
69      /* ------------------------------------------------------------ */
70      /** Constructor. 
71       * @param ignoreCase 
72       * @param width Width of hash tables, larger values are faster but
73       * use more memory.
74       */
75      public StringMap(boolean ignoreCase,int width)
76      {
77          this();
78          _ignoreCase=ignoreCase;
79          _width=width;
80      }
81      
82      /* ------------------------------------------------------------ */
83      /** Set the ignoreCase attribute.
84       * @param ic If true, the map is case insensitive for keys.
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     /** Set the hash width.
101      * @param width Width of hash tables, larger values are faster but
102      * use more memory.
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         // look for best match
144     charLoop:
145         for (int i=0;i<key.length();i++)
146         {
147             char c=key.charAt(i);
148             
149             // Advance node
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             // Loop through a node chain at the same level
159             while (node!=null) 
160             {
161                 // If it is a matching node, goto next char
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                 // no char match
172                 // if the first char,
173                 if (ni==0)
174                 {
175                     // look along the chain for a char match
176                     prev=node;
177                     node=node._next;
178                 }
179                 else
180                 {
181                     // Split the current node!
182                     node.split(this,ni);
183                     i--;
184                     ni=-1;
185                     continue charLoop;
186                 }
187             }
188 
189             // We have run out of nodes, so as this is a put, make one
190             node = new Node(_ignoreCase,key,i);
191 
192             if (prev!=null) // add to end of chain
193                 prev._next=node;
194             else if (parent!=null) // add new child
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 // this is the root.
214                 _root=node;
215             break;
216         }
217         
218         // Do we have a node
219         if (node!=null)
220         {
221             // Split it if we are in the middle
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     /** Get a map entry by substring key.
258      * @param key String containing the key
259      * @param offset Offset of the key within the String.
260      * @param length The length of the key 
261      * @return The Map.Entry for the key or null if the key is not in
262      * the map.
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         // look for best match
273     charLoop:
274         for (int i=0;i<length;i++)
275         {
276             char c=key.charAt(offset+i);
277 
278             // Advance node
279             if (ni==-1)
280             {
281                 ni=0;
282                 node=(node._children==null)?null:node._children[c%_width];
283             }
284             
285             // Look through the node chain
286             while (node!=null) 
287             {
288                 // If it is a matching node, goto next char
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                 // No char match, so if mid node then no match at all.
298                 if (ni>0) return null;
299 
300                 // try next in chain
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     /** Get a map entry by char array key.
314      * @param key char array containing the key
315      * @param offset Offset of the key within the array.
316      * @param length The length of the key 
317      * @return The Map.Entry for the key or null if the key is not in
318      * the map.
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         // look for best match
329     charLoop:
330         for (int i=0;i<length;i++)
331         {
332             char c=key[offset+i];
333 
334             // Advance node
335             if (ni==-1)
336             {
337                 ni=0;
338                 node=(node._children==null)?null:node._children[c%_width];
339             }
340             
341             // While we have a node to try
342             while (node!=null) 
343             {
344                 // If it is a matching node, goto next char
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                 // No char match, so if mid node then no match at all.
354                 if (ni>0) return null;
355 
356                 // try next in chain
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     /** Get a map entry by byte array key, using as much of the passed key as needed for a match.
370      * A simple 8859-1 byte to char mapping is assumed.
371      * @param key char array containing the key
372      * @param offset Offset of the key within the array.
373      * @param maxLength The length of the key 
374      * @return The Map.Entry for the key or null if the key is not in
375      * the map.
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         // look for best match
386     charLoop:
387         for (int i=0;i<maxLength;i++)
388         {
389             char c=(char)key[offset+i];
390 
391             // Advance node
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; // This is the best match
400                 node=child;           
401             }
402             
403             // While we have a node to try
404             while (node!=null) 
405             {
406                 // If it is a matching node, goto next char
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                 // No char match, so if mid node then no match at all.
416                 if (ni>0) return null;
417 
418                 // try next in chain
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         // look for best match
458     charLoop:
459         for (int i=0;i<key.length();i++)
460         {
461             char c=key.charAt(i);
462 
463             // Advance node
464             if (ni==-1)
465             {
466                 ni=0;
467                 node=(node._children==null)?null:node._children[c%_width];
468             }
469             
470             // While we have a node to try
471             while (node!=null) 
472             {
473                 // If it is a matching node, goto next char
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                 // No char match, so if mid node then no match at all.
483                 if (ni>0) return null;
484 
485                 // try next in chain
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 }