StringMap


1   // ========================================================================
2   // $Id: StringMap.java,v 1.13 2004/10/23 09:03:22 gregwilkins Exp $
3   // Copyright 1997-2004 Mort Bay Consulting Pty. Ltd.
4   // ------------------------------------------------------------------------
5   // Licensed under the Apache License, Version 2.0 (the "License");
6   // you may not use this file except in compliance with the License.
7   // You may obtain a copy of the License at 
8   // http://www.apache.org/licenses/LICENSE-2.0
9   // Unless required by applicable law or agreed to in writing, software
10  // distributed under the License is distributed on an "AS IS" BASIS,
11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  // See the License for the specific language governing permissions and
13  // limitations under the License.
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 like class of Strings to Objects.
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   * @version $Id: StringMap.java,v 1.13 2004/10/23 09:03:22 gregwilkins Exp $
38   * @author Greg Wilkins (gregw)
39   */
40  public class StringMap extends AbstractMap   implements Externalizable  
41  {
42      private static final int __HASH_WIDTH=9;
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          _ignoreCase=ignoreCase;
66      }
67      
68      /* ------------------------------------------------------------ */
69      /** Constructor. 
70       * @param ignoreCase 
71       * @param width Width of hash tables, larger values are faster but
72       * use more memory.
73       */
74      public StringMap(boolean ignoreCase,int width)
75      {
76          _ignoreCase=ignoreCase;
77          _width=width;
78      }
79      
80      /* ------------------------------------------------------------ */
81      /** Set the ignoreCase attribute.
82       * @param ic If true, the map is case insensitive for keys.
83       */
84      public void setIgnoreCase(boolean ic)
85      {
86          if (_root._children!=null)
87              throw new IllegalStateException  ("Must be set before first put");
88          _ignoreCase=ic;
89      }
90  
91      /* ------------------------------------------------------------ */
92      public boolean isIgnoreCase()
93      {
94          return _ignoreCase;
95      }
96  
97      /* ------------------------------------------------------------ */
98      /** Set the hash width.
99       * @param width Width of hash tables, larger values are faster but
100      * use more memory.
101      */
102     public void setWidth(int width)
103     {
104         _width=width;
105     }
106 
107     /* ------------------------------------------------------------ */
108     public int getWidth()
109     {
110         return _width;
111     }
112     
113     /* ------------------------------------------------------------ */
114     public Object   put(Object   key, Object   value)
115     {
116         if (key==null)
117             return put(null,value);
118         return put(key.toString(),value);
119     }
120         
121     /* ------------------------------------------------------------ */
122     public Object   put(String   key, Object   value)
123     {
124         if (key==null)
125         {
126             Object   oldValue=_nullValue;
127             _nullValue=value;
128             if (_nullEntry==null)
129             {   
130                 _nullEntry=new NullEntry();
131                 _entrySet.add(_nullEntry);
132             }
133             return oldValue;
134         }
135         
136         Node node = _root;
137         int ni=-1;
138         Node prev = null;
139         Node parent = null;
140 
141         // look for best match
142     charLoop:
143         for (int i=0;i<key.length();i++)
144         {
145             char c=key.charAt(i);
146             
147             // Advance node
148             if (ni==-1)
149             {
150                 parent=node;
151                 prev=null;
152                 ni=0;
153                 node=(node._children==null)?null:node._children[c%_width];
154             }
155             
156             // Loop through a node chain at the same level
157             while (node!=null) 
158             {
159                 // If it is a matching node, goto next char
160                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
161                 {
162                     prev=null;
163                     ni++;
164                     if (ni==node._char.length)
165                         ni=-1;
166                     continue charLoop;
167                 }
168 
169                 // no char match
170                 // if the first char,
171                 if (ni==0)
172                 {
173                     // look along the chain for a char match
174                     prev=node;
175                     node=node._next;
176                 }
177                 else
178                 {
179                     // Split the current node!
180                     node.split(this,ni);
181                     i--;
182                     ni=-1;
183                     continue charLoop;
184                 }
185             }
186 
187             // We have run out of nodes, so as this is a put, make one
188             node = new Node(_ignoreCase,key,i);
189 
190             if (prev!=null) // add to end of chain
191                 prev._next=node;
192             else if (parent!=null) // add new child
193             {
194                 if (parent._children==null)
195                     parent._children=new Node[_width];
196                 parent._children[c%_width]=node;
197                 int oi=node._ochar[0]%_width;
198                 if (node._ochar!=null && node._char[0]%_width!=oi)
199                 {
200                     if (parent._children[oi]==null)
201                         parent._children[oi]=node;
202                     else
203                     {
204                         Node n=parent._children[oi];
205                         while(n._next!=null)
206                             n=n._next;
207                         n._next=node;
208                     }
209                 }
210             }
211             else // this is the root.
212                 _root=node;
213             break;
214         }
215         
216         // Do we have a node
217         if (node!=null)
218         {
219             // Split it if we are in the middle
220             if(ni>0)
221                 node.split(this,ni);
222         
223             Object   old = node._value;
224             node._key=key;
225             node._value=value;
226             _entrySet.add(node);
227             return old;
228         }
229         return null;
230     }
231     
232     /* ------------------------------------------------------------ */
233     public Object   get(Object   key)
234     {
235         if (key==null)
236             return _nullValue;
237         if (key instanceof String  )
238             return get((String  )key);
239         return get(key.toString());
240     }
241     
242     /* ------------------------------------------------------------ */
243     public Object   get(String   key)
244     {
245         if (key==null)
246             return _nullValue;
247         
248         Map.Entry   entry = getEntry(key,0,key.length());
249         if (entry==null)
250             return null;
251         return entry.getValue();
252     }
253     
254     /* ------------------------------------------------------------ */
255     /** Get a map entry by substring key.
256      * @param key String containing the key
257      * @param offset Offset of the key within the String.
258      * @param length The length of the key 
259      * @return The Map.Entry for the key or null if the key is not in
260      * the map.
261      */
262     public Map.Entry   getEntry(String   key,int offset, int length)
263     {
264         if (key==null)
265             return _nullEntry;
266         
267         Node node = _root;
268         int ni=-1;
269 
270         // look for best match
271     charLoop:
272         for (int i=0;i<length;i++)
273         {
274             char c=key.charAt(offset+i);
275 
276             // Advance node
277             if (ni==-1)
278             {
279                 ni=0;
280                 node=(node._children==null)?null:node._children[c%_width];
281             }
282             
283             // Look through the node chain
284             while (node!=null) 
285             {
286                 // If it is a matching node, goto next char
287                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
288                 {
289                     ni++;
290                     if (ni==node._char.length)
291                         ni=-1;
292                     continue charLoop;
293                 }
294 
295                 // No char match, so if mid node then no match at all.
296                 if (ni>0) return null;
297 
298                 // try next in chain
299                 node=node._next;                
300             }
301             return null;
302         }
303         
304         if (ni>0) return null;
305         if (node!=null && node._key==null)
306             return null;
307         return node;
308     }
309     
310     /* ------------------------------------------------------------ */
311     /** Get a map entry by char array key.
312      * @param key char array containing the key
313      * @param offset Offset of the key within the array.
314      * @param length The length of the key 
315      * @return The Map.Entry for the key or null if the key is not in
316      * the map.
317      */
318     public Map.Entry   getEntry(char[] key,int offset, int length)
319     {
320         if (key==null)
321             return _nullEntry;
322         
323         Node node = _root;
324         int ni=-1;
325 
326         // look for best match
327     charLoop:
328         for (int i=0;i<length;i++)
329         {
330             char c=key[offset+i];
331 
332             // Advance node
333             if (ni==-1)
334             {
335                 ni=0;
336                 node=(node._children==null)?null:node._children[c%_width];
337             }
338             
339             // While we have a node to try
340             while (node!=null) 
341             {
342                 // If it is a matching node, goto next char
343                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
344                 {
345                     ni++;
346                     if (ni==node._char.length)
347                         ni=-1;
348                     continue charLoop;
349                 }
350 
351                 // No char match, so if mid node then no match at all.
352                 if (ni>0) return null;
353 
354                 // try next in chain
355                 node=node._next;                
356             }
357             return null;
358         }
359         
360         if (ni>0) return null;
361         if (node!=null && node._key==null)
362             return null;
363         return node;
364     }
365     
366     /* ------------------------------------------------------------ */
367     /** Get a map entry by byte array key.
368      * @param key byte array containing the key. A simple ASCII byte
369      * to char mapping is used.
370      * @param offset Offset of the key within the array.
371      * @param length The length of the key 
372      * @return The Map.Entry for the key or null if the key is not in
373      * the map.
374      */
375     public Map.Entry   getEntry(byte[] key,int offset, int length)
376     {
377         if (key==null)
378             return _nullEntry;
379         
380         Node node = _root;
381         int ni=-1;
382 
383         // look for best match
384     charLoop:
385         for (int i=0;i<length;i++)
386         {
387             char c=(char)(key[offset+i]);
388 
389             // Advance node
390             if (ni==-1)
391             {
392                 ni=0;
393                 node=(node._children==null)?null:node._children[c%_width];
394             }
395             
396             // While we have a node to try
397             while (node!=null) 
398             {  
399                 // If it is a matching node, goto next char
400                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
401                 {
402                     ni++;
403                     if (ni==node._char.length)
404                         ni=-1;
405                     continue charLoop;
406                 }
407 
408                 // No char match, so if mid node then no match at all.
409                 if (ni>0) return null;
410 
411                 // try next in chain
412                 node=node._next;                      
413             }
414             return null;
415         }
416         
417         if (ni>0) return null;
418         if (node!=null && node._key==null)
419             return null;
420         return node;
421     }
422     
423     /* ------------------------------------------------------------ */
424     public Object   remove(Object   key)
425     {
426         if (key==null)
427             return remove(null);
428         return remove(key.toString());
429     }
430     
431     /* ------------------------------------------------------------ */
432     public Object   remove(String   key)
433     {
434         if (key==null)
435         {
436             Object   oldValue=_nullValue;
437             if (_nullEntry!=null)
438             {
439                 _entrySet.remove(_nullEntry);   
440                 _nullEntry=null;
441                 _nullValue=null;
442             }
443             return oldValue;
444         }
445         
446         Node node = _root;
447         int ni=-1;
448 
449         // look for best match
450     charLoop:
451         for (int i=0;i<key.length();i++)
452         {
453             char c=key.charAt(i);
454 
455             // Advance node
456             if (ni==-1)
457             {
458                 ni=0;
459                 node=(node._children==null)?null:node._children[c%_width];
460             }
461             
462             // While we have a node to try
463             while (node!=null) 
464             {
465                 // If it is a matching node, goto next char
466                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
467                 {
468                     ni++;
469                     if (ni==node._char.length)
470                         ni=-1;
471                     continue charLoop;
472                 }
473 
474                 // No char match, so if mid node then no match at all.
475                 if (ni>0) return null;
476 
477                 // try next in chain
478                 node=node._next;         
479             }
480             return null;
481         }
482 
483         if (ni>0) return null;
484         if (node==null || node._key==null)
485             return null;
486         
487         Object   old = node._value;
488         _entrySet.remove(node);
489         node._value=null;
490         node._key=null;
491         
492         return old; 
493     }
494 
495     /* ------------------------------------------------------------ */
496     public Set   entrySet()
497     {
498         return _umEntrySet;
499     }
500     
501     /* ------------------------------------------------------------ */
502     public int size()
503     {
504         return _entrySet.size();
505     }
506 
507     /* ------------------------------------------------------------ */
508     public boolean isEmpty()
509     {
510         return _entrySet.isEmpty();
511     }
512 
513     /* ------------------------------------------------------------ */
514     public boolean containsKey(Object   key)
515     {
516         if (key==null)
517             return _nullEntry!=null;
518         return
519             getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
520     }
521     
522     /* ------------------------------------------------------------ */
523     public void clear()
524     {
525         _root=new Node();
526         _nullEntry=null;
527         _nullValue=null;
528         _entrySet.clear();
529     }
530 
531     
532     /* ------------------------------------------------------------ */
533     /* ------------------------------------------------------------ */
534     /* ------------------------------------------------------------ */
535     private static class Node implements Map.Entry  
536     {
537         char[] _char;
538         char[] _ochar;
539         Node _next;
540         Node[] _children;
541         String   _key;
542         Object   _value;
543         
544         Node(){}
545         
546         Node(boolean ignoreCase,String   s, int offset)
547         {
548             int l=s.length()-offset;
549             _char=new char[l];
550             _ochar=new char[l];
551             for (int i=0;i<l;i++)
552             {
553                 char c=s.charAt(offset+i);
554                 _char[i]=c;
555                 if (ignoreCase)
556                 {
557                     char o=c;
558                     if (Character.isUpperCase(c))
559                         o=Character.toLowerCase(c);
560                     else if (Character.isLowerCase(c))
561                         o=Character.toUpperCase(c);
562                     _ochar[i]=o;
563                 }
564             }
565         }
566 
567         Node split(StringMap map,int offset)
568         {
569             Node split = new Node();
570             int sl=_char.length-offset;
571             
572             char[] tmp=this._char;
573             this._char=new char[offset];
574             split._char = new char[sl];
575             System.arraycopy(tmp,0,this._char,0,offset);
576             System.arraycopy(tmp,offset,split._char,0,sl);
577 
578             if (this._ochar!=null)
579             {
580                 tmp=this._ochar;
581                 this._ochar=new char[offset];
582                 split._ochar = new char[sl];
583                 System.arraycopy(tmp,0,this._ochar,0,offset);
584                 System.arraycopy(tmp,offset,split._ochar,0,sl);
585             }
586             
587             split._key=this._key;
588             split._value=this._value;
589             this._key=null;
590             this._value=null;
591             if (map._entrySet.remove(this))
592                 map._entrySet.add(split);
593 
594             split._children=this._children;            
595             this._children=new Node[map._width];
596             this._children[split._char[0]%map._width]=split;
597             if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
598                 this._children[split._ochar[0]%map._width]=split;
599 
600             return split;
601         }
602         
603         public Object   getKey(){return _key;}
604         public Object   getValue(){return _value;}
605         public Object   setValue(Object   o){Object   old=_value;_value=o;return old;}
606         public String   toString()
607         {
608             StringBuffer   buf=new StringBuffer  ();
609             synchronized(buf)
610             {
611                 toString(buf);
612             }
613             return buf.toString();
614         }
615 
616         private void toString(StringBuffer   buf)
617         {
618             buf.append("{[");
619             if (_char==null)
620                 buf.append('-');
621             else
622                 for (int i=0;i<_char.length;i++)
623                     buf.append(_char[i]);
624             buf.append(':');
625             buf.append(_key);
626             buf.append('=');
627             buf.append(_value);
628             buf.append(']');
629             if (_children!=null)
630             {
631                 for (int i=0;i<_children.length;i++)
632                 {
633                     buf.append('|');
634                     if (_children[i]!=null)
635                         _children[i].toString(buf);
636                     else
637                         buf.append("-");
638                 }
639             }
640             buf.append('}');
641             if (_next!=null)
642             {
643                 buf.append(",\n");
644                 _next.toString(buf);
645             }
646         }
647     }
648 
649     /* ------------------------------------------------------------ */
650     /* ------------------------------------------------------------ */
651     private class NullEntry implements Map.Entry  
652     {
653         public Object   getKey(){return null;}
654         public Object   getValue(){return _nullValue;}
655         public Object   setValue(Object   o)
656             {Object   old=_nullValue;_nullValue=o;return old;}
657         public String   toString(){return "[:null="+_nullValue+"]";}
658     }
659 
660     /* ------------------------------------------------------------ */
661     public void writeExternal(java.io.ObjectOutput   out)
662         throws java.io.IOException  
663     {
664         HashMap   map = new HashMap  (this);
665         out.writeObject(map);
666     }
667     
668     /* ------------------------------------------------------------ */
669     public void readExternal(java.io.ObjectInput   in)
670         throws java.io.IOException  , ClassNotFoundException  
671     {
672         HashMap   map = (HashMap  )in.readObject();
673         this.putAll(map);
674     }
675 }
676
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags