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 }