Source Code Cross Referenced for StringMap.java in  » Sevlet-Container » jetty-modules » org » mortbay » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Sevlet Container » jetty modules » org.mortbay.util 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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