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: }
|