001    package railo.commons.collections;
002    
003    import java.io.Externalizable;
004    import java.util.AbstractMap;
005    import java.util.Collections;
006    import java.util.HashMap;
007    import java.util.HashSet;
008    import java.util.Map;
009    import java.util.Set;
010    
011    /** Map implementation Optimized for Strings keys..
012     * This String Map has been optimized for mapping small sets of
013     * Strings where the most frequently accessed Strings have been put to
014     * the map first.
015     *
016     * It also has the benefit that it can look up entries by substring or
017     * sections of char and byte arrays.  This can prevent many String
018     * objects from being created just to look up in the map.
019     *
020     * This map is NOT synchronized.
021     */
022    public class StringMap extends AbstractMap implements Externalizable
023    {
024        public static final boolean CASE_INSENSTIVE=true;
025        protected static final int __HASH_WIDTH=17;
026        
027        /* ------------------------------------------------------------ */
028        protected int _width=__HASH_WIDTH;
029        protected Node _root=new Node();
030        protected boolean _ignoreCase=false;
031        protected NullEntry _nullEntry=null;
032        protected Object _nullValue=null;
033            protected HashSet _entrySet=new HashSet(3);
034            protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet);
035        
036        /* ------------------------------------------------------------ */
037        /** Constructor. 
038         */
039        public StringMap()
040        {}
041        
042        /* ------------------------------------------------------------ */
043        /** Constructor. 
044         * @param ignoreCase 
045         */
046        public StringMap(boolean ignoreCase)
047        {
048            this();
049            _ignoreCase=ignoreCase;
050        }
051        
052        /* ------------------------------------------------------------ */
053        /** Constructor. 
054         * @param ignoreCase 
055         * @param width Width of hash tables, larger values are faster but
056         * use more memory.
057         */
058        public StringMap(boolean ignoreCase,int width)
059        {
060            this();
061            _ignoreCase=ignoreCase;
062            _width=width;
063        }
064        
065        /* ------------------------------------------------------------ */
066        /** Set the ignoreCase attribute.
067         * @param ic If true, the map is case insensitive for keys.
068         */
069        public void setIgnoreCase(boolean ic)
070        {
071            if (_root._children!=null)
072                throw new IllegalStateException("Must be set before first put");
073            _ignoreCase=ic;
074        }
075    
076        /* ------------------------------------------------------------ */
077        public boolean isIgnoreCase()
078        {
079            return _ignoreCase;
080        }
081    
082        /* ------------------------------------------------------------ */
083        /** Set the hash width.
084         * @param width Width of hash tables, larger values are faster but
085         * use more memory.
086         */
087        public void setWidth(int width)
088        {
089            _width=width;
090        }
091    
092        /* ------------------------------------------------------------ */
093        public int getWidth()
094        {
095            return _width;
096        }
097        
098        /* ------------------------------------------------------------ */
099        public Object put(Object key, Object value)
100        {
101            if (key==null)
102                return put(null,value);
103            return put(key.toString(),value);
104        }
105            
106        /* ------------------------------------------------------------ */
107        public Object put(String key, Object value)
108        {
109            if (key==null)
110            {
111                Object oldValue=_nullValue;
112                _nullValue=value;
113                if (_nullEntry==null)
114                {   
115                    _nullEntry=new NullEntry();
116                    _entrySet.add(_nullEntry);
117                }
118                return oldValue;
119            }
120            
121            Node node = _root;
122            int ni=-1;
123            Node prev = null;
124            Node parent = null;
125    
126            // look for best match
127        charLoop:
128            for (int i=0;i<key.length();i++)
129            {
130                char c=key.charAt(i);
131                
132                // Advance node
133                if (ni==-1)
134                {
135                    parent=node;
136                    prev=null;
137                    ni=0;
138                    node=(node._children==null)?null:node._children[c%_width];
139                }
140                
141                // Loop through a node chain at the same level
142                while (node!=null) 
143                {
144                    // If it is a matching node, goto next char
145                    if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
146                    {
147                        prev=null;
148                        ni++;
149                        if (ni==node._char.length)
150                            ni=-1;
151                        continue charLoop;
152                    }
153    
154                    // no char match
155                    // if the first char,
156                    if (ni==0)
157                    {
158                        // look along the chain for a char match
159                        prev=node;
160                        node=node._next;
161                    }
162                    else
163                    {
164                        // Split the current node!
165                        node.split(this,ni);
166                        i--;
167                        ni=-1;
168                        continue charLoop;
169                    }
170                }
171    
172                // We have run out of nodes, so as this is a put, make one
173                node = new Node(_ignoreCase,key,i);
174    
175                if (prev!=null) // add to end of chain
176                    prev._next=node;
177                else if (parent!=null) // add new child
178                {
179                    if (parent._children==null)
180                        parent._children=new Node[_width];
181                    parent._children[c%_width]=node;
182                    int oi=node._ochar[0]%_width;
183                    if (node._ochar!=null && node._char[0]%_width!=oi)
184                    {
185                        if (parent._children[oi]==null)
186                            parent._children[oi]=node;
187                        else
188                        {
189                            Node n=parent._children[oi];
190                            while(n._next!=null)
191                                n=n._next;
192                            n._next=node;
193                        }
194                    }
195                }
196                else // this is the root.
197                    _root=node;
198                break;
199            }
200            
201            // Do we have a node
202            if (node!=null)
203            {
204                // Split it if we are in the middle
205                if(ni>0)
206                    node.split(this,ni);
207            
208                Object old = node._value;
209                node._key=key;
210                node._value=value;
211                _entrySet.add(node);
212                return old;
213            }
214            return null;
215        }
216        
217        /* ------------------------------------------------------------ */
218        public Object get(Object key)
219        {
220            if (key==null)
221                return _nullValue;
222            if (key instanceof String)
223                return get((String)key);
224            return get(key.toString());
225        }
226        
227        /* ------------------------------------------------------------ */
228        public Object get(String key)
229        {
230            if (key==null)
231                return _nullValue;
232            
233            Map.Entry entry = getEntry(key,0,key.length());
234            if (entry==null)
235                return null;
236            return entry.getValue();
237        }
238        
239        /* ------------------------------------------------------------ */
240        /** Get a map entry by substring key.
241         * @param key String containing the key
242         * @param offset Offset of the key within the String.
243         * @param length The length of the key 
244         * @return The Map.Entry for the key or null if the key is not in
245         * the map.
246         */
247        public Map.Entry getEntry(String key,int offset, int length)
248        {
249            if (key==null)
250                return _nullEntry;
251            
252            Node node = _root;
253            int ni=-1;
254    
255            // look for best match
256        charLoop:
257            for (int i=0;i<length;i++)
258            {
259                char c=key.charAt(offset+i);
260    
261                // Advance node
262                if (ni==-1)
263                {
264                    ni=0;
265                    node=(node._children==null)?null:node._children[c%_width];
266                }
267                
268                // Look through the node chain
269                while (node!=null) 
270                {
271                    // If it is a matching node, goto next char
272                    if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
273                    {
274                        ni++;
275                        if (ni==node._char.length)
276                            ni=-1;
277                        continue charLoop;
278                    }
279    
280                    // No char match, so if mid node then no match at all.
281                    if (ni>0) return null;
282    
283                    // try next in chain
284                    node=node._next;                
285                }
286                return null;
287            }
288            
289            if (ni>0) return null;
290            if (node!=null && node._key==null)
291                return null;
292            return node;
293        }
294        
295        /* ------------------------------------------------------------ */
296        /** Get a map entry by char array key.
297         * @param key char array containing the key
298         * @param offset Offset of the key within the array.
299         * @param length The length of the key 
300         * @return The Map.Entry for the key or null if the key is not in
301         * the map.
302         */
303        public Map.Entry getEntry(char[] key,int offset, int length)
304        {
305            if (key==null)
306                return _nullEntry;
307            
308            Node node = _root;
309            int ni=-1;
310    
311            // look for best match
312        charLoop:
313            for (int i=0;i<length;i++)
314            {
315                char c=key[offset+i];
316    
317                // Advance node
318                if (ni==-1)
319                {
320                    ni=0;
321                    node=(node._children==null)?null:node._children[c%_width];
322                }
323                
324                // While we have a node to try
325                while (node!=null) 
326                {
327                    // If it is a matching node, goto next char
328                    if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
329                    {
330                        ni++;
331                        if (ni==node._char.length)
332                            ni=-1;
333                        continue charLoop;
334                    }
335    
336                    // No char match, so if mid node then no match at all.
337                    if (ni>0) return null;
338    
339                    // try next in chain
340                    node=node._next;                
341                }
342                return null;
343            }
344            
345            if (ni>0) return null;
346            if (node!=null && node._key==null)
347                return null;
348            return node;
349        }
350    
351        /* ------------------------------------------------------------ */
352        /** Get a map entry by byte array key, using as much of the passed key as needed for a match.
353         * A simple 8859-1 byte to char mapping is assumed.
354         * @param key char array containing the key
355         * @param offset Offset of the key within the array.
356         * @param maxLength The length of the key 
357         * @return The Map.Entry for the key or null if the key is not in
358         * the map.
359         */
360        public Map.Entry getBestEntry(byte[] key,int offset, int maxLength)
361        {
362            if (key==null)
363                return _nullEntry;
364            
365            Node node = _root;
366            int ni=-1;
367    
368            // look for best match
369        charLoop:
370            for (int i=0;i<maxLength;i++)
371            {
372                char c=(char)key[offset+i];
373    
374                // Advance node
375                if (ni==-1)
376                {
377                    ni=0;
378                    
379                    Node child = (node._children==null)?null:node._children[c%_width];
380                    
381                    if (child==null && i>0)
382                        return node; // This is the best match
383                    node=child;           
384                }
385                
386                // While we have a node to try
387                while (node!=null) 
388                {
389                    // If it is a matching node, goto next char
390                    if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
391                    {
392                        ni++;
393                        if (ni==node._char.length)
394                            ni=-1;
395                        continue charLoop;
396                    }
397    
398                    // No char match, so if mid node then no match at all.
399                    if (ni>0) return null;
400    
401                    // try next in chain
402                    node=node._next;                
403                }
404                return null;
405            }
406            
407            if (ni>0) return null;
408            if (node!=null && node._key==null)
409                return null;
410            return node;
411        }
412        
413        
414        /* ------------------------------------------------------------ */
415        public Object remove(Object key)
416        {
417            if (key==null)
418                return remove(null);
419            return remove(key.toString());
420        }
421        
422        /* ------------------------------------------------------------ */
423        public Object remove(String key)
424        {
425            if (key==null)
426            {
427                Object oldValue=_nullValue;
428                if (_nullEntry!=null)
429                {
430                    _entrySet.remove(_nullEntry);   
431                    _nullEntry=null;
432                    _nullValue=null;
433                }
434                return oldValue;
435            }
436            
437            Node node = _root;
438            int ni=-1;
439    
440            // look for best match
441        charLoop:
442            for (int i=0;i<key.length();i++)
443            {
444                char c=key.charAt(i);
445    
446                // Advance node
447                if (ni==-1)
448                {
449                    ni=0;
450                    node=(node._children==null)?null:node._children[c%_width];
451                }
452                
453                // While we have a node to try
454                while (node!=null) 
455                {
456                    // If it is a matching node, goto next char
457                    if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
458                    {
459                        ni++;
460                        if (ni==node._char.length)
461                            ni=-1;
462                        continue charLoop;
463                    }
464    
465                    // No char match, so if mid node then no match at all.
466                    if (ni>0) return null;
467    
468                    // try next in chain
469                    node=node._next;         
470                }
471                return null;
472            }
473    
474            if (ni>0) return null;
475            if (node!=null && node._key==null)
476                return null;
477            
478            Object old = node._value;
479            _entrySet.remove(node);
480            node._value=null;
481            node._key=null;
482            
483            return old; 
484        }
485    
486        /* ------------------------------------------------------------ */
487        public Set entrySet()
488        {
489            return _umEntrySet;
490        }
491        
492        /* ------------------------------------------------------------ */
493        public int size()
494        {
495            return _entrySet.size();
496        }
497    
498        /* ------------------------------------------------------------ */
499        public boolean isEmpty()
500        {
501            return _entrySet.isEmpty();
502        }
503    
504        /* ------------------------------------------------------------ */
505        public boolean containsKey(Object key)
506        {
507            if (key==null)
508                return _nullEntry!=null;
509            return
510                getEntry(key.toString(),0,key.toString().length())!=null;
511        }
512        
513        /* ------------------------------------------------------------ */
514        public void clear()
515        {
516            _root=new Node();
517            _nullEntry=null;
518            _nullValue=null;
519            _entrySet.clear();
520        }
521    
522        
523        /* ------------------------------------------------------------ */
524        /* ------------------------------------------------------------ */
525        /* ------------------------------------------------------------ */
526        private static class Node implements Map.Entry
527        {
528            char[] _char;
529            char[] _ochar;
530            Node _next;
531            Node[] _children;
532            String _key;
533            Object _value;
534            
535            Node(){}
536            
537            Node(boolean ignoreCase,String s, int offset)
538            {
539                int l=s.length()-offset;
540                _char=new char[l];
541                _ochar=new char[l];
542                for (int i=0;i<l;i++)
543                {
544                    char c=s.charAt(offset+i);
545                    _char[i]=c;
546                    if (ignoreCase)
547                    {
548                        char o=c;
549                        if (Character.isUpperCase(c))
550                            o=Character.toLowerCase(c);
551                        else if (Character.isLowerCase(c))
552                            o=Character.toUpperCase(c);
553                        _ochar[i]=o;
554                    }
555                }
556            }
557    
558            Node split(StringMap map,int offset)
559            {
560                Node split = new Node();
561                int sl=_char.length-offset;
562                
563                char[] tmp=this._char;
564                this._char=new char[offset];
565                split._char = new char[sl];
566                System.arraycopy(tmp,0,this._char,0,offset);
567                System.arraycopy(tmp,offset,split._char,0,sl);
568    
569                if (this._ochar!=null)
570                {
571                    tmp=this._ochar;
572                    this._ochar=new char[offset];
573                    split._ochar = new char[sl];
574                    System.arraycopy(tmp,0,this._ochar,0,offset);
575                    System.arraycopy(tmp,offset,split._ochar,0,sl);
576                }
577                
578                split._key=this._key;
579                split._value=this._value;
580                this._key=null;
581                this._value=null;
582                if (map._entrySet.remove(this))
583                    map._entrySet.add(split);
584    
585                split._children=this._children;            
586                this._children=new Node[map._width];
587                this._children[split._char[0]%map._width]=split;
588                if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
589                    this._children[split._ochar[0]%map._width]=split;
590    
591                return split;
592            }
593            
594            public Object getKey(){return _key;}
595            public Object getValue(){return _value;}
596            public Object setValue(Object o){Object old=_value;_value=o;return old;}
597            public String toString()
598            {
599                StringBuffer buf=new StringBuffer();
600                synchronized(buf)
601                {
602                    toString(buf);
603                }
604                return buf.toString();
605            }
606    
607            private void toString(StringBuffer buf)
608            {
609                buf.append("{[");
610                if (_char==null)
611                    buf.append('-');
612                else
613                    for (int i=0;i<_char.length;i++)
614                        buf.append(_char[i]);
615                buf.append(':');
616                buf.append(_key);
617                buf.append('=');
618                buf.append(_value);
619                buf.append(']');
620                if (_children!=null)
621                {
622                    for (int i=0;i<_children.length;i++)
623                    {
624                        buf.append('|');
625                        if (_children[i]!=null)
626                            _children[i].toString(buf);
627                        else
628                            buf.append("-");
629                    }
630                }
631                buf.append('}');
632                if (_next!=null)
633                {
634                    buf.append(",\n");
635                    _next.toString(buf);
636                }
637            }
638        }
639    
640        /* ------------------------------------------------------------ */
641        /* ------------------------------------------------------------ */
642        private class NullEntry implements Map.Entry
643        {
644            public Object getKey(){return null;}
645            public Object getValue(){return _nullValue;}
646            public Object setValue(Object o)
647                {Object old=_nullValue;_nullValue=o;return old;}
648            public String toString(){return "[:null="+_nullValue+"]";}
649        }
650    
651        /* ------------------------------------------------------------ */
652        public void writeExternal(java.io.ObjectOutput out)
653            throws java.io.IOException
654        {
655            HashMap map = new HashMap(this);
656            out.writeBoolean(_ignoreCase);
657            out.writeObject(map);
658        }
659        
660        /* ------------------------------------------------------------ */
661        public void readExternal(java.io.ObjectInput in)
662            throws java.io.IOException, ClassNotFoundException
663        {
664            boolean ic=in.readBoolean();
665            HashMap map = (HashMap)in.readObject();
666            setIgnoreCase(ic);
667            this.putAll(map);
668        }
669    }