001/* 002 * This file is part of McIDAS-V 003 * 004 * Copyright 2007-2023 005 * Space Science and Engineering Center (SSEC) 006 * University of Wisconsin - Madison 007 * 1225 W. Dayton Street, Madison, WI 53706, USA 008 * https://www.ssec.wisc.edu/mcidas 009 * 010 * All Rights Reserved 011 * 012 * McIDAS-V is built on Unidata's IDV and SSEC's VisAD libraries, and 013 * some McIDAS-V source code is based on IDV and VisAD source code. 014 * 015 * McIDAS-V is free software; you can redistribute it and/or modify 016 * it under the terms of the GNU Lesser Public License as published by 017 * the Free Software Foundation; either version 3 of the License, or 018 * (at your option) any later version. 019 * 020 * McIDAS-V is distributed in the hope that it will be useful, 021 * but WITHOUT ANY WARRANTY; without even the implied warranty of 022 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 023 * GNU Lesser Public License for more details. 024 * 025 * You should have received a copy of the GNU Lesser Public License 026 * along with this program. If not, see http://www.gnu.org/licenses. 027 */ 028package edu.wisc.ssec.mcidasv.util.trie; 029 030import java.io.Serializable; 031import java.util.AbstractCollection; 032import java.util.AbstractMap; 033import java.util.AbstractSet; 034import java.util.Collection; 035import java.util.Comparator; 036import java.util.ConcurrentModificationException; 037import java.util.Iterator; 038import java.util.Map; 039import java.util.NoSuchElementException; 040import java.util.Set; 041import java.util.SortedMap; 042 043/** 044 * A PATRICIA Trie. 045 * <p> 046 * PATRICIA = Practical Algorithm to Retrieve Information Coded in Alphanumeric 047 * <p> 048 * A PATRICIA Trie is a compressed Trie. Instead of storing all data at the 049 * edges of the Trie (and having empty internal nodes), PATRICIA stores data 050 * in every node. This allows for very efficient traversal, insert, delete, 051 * predecessor, successor, prefix, range, and 'select' operations. All operations 052 * are performed at worst in O(K) time, where K is the number of bits in the 053 * largest item in the tree. In practice, operations actually take O(A(K)) 054 * time, where A(K) is the average number of bits of all items in the tree. 055 * <p> 056 * Most importantly, PATRICIA requires very few comparisons to keys while 057 * doing any operation. While performing a lookup, each comparison 058 * (at most K of them, described above) will perform a single bit comparison 059 * against the given key, instead of comparing the entire key to another key. 060 * <p> 061 * The Trie can return operations in lexicographical order using the 'traverse', 062 * 'prefix', 'submap', or 'iterator' methods. The Trie can also scan for items 063 * that are 'bitwise' (using an XOR metric) by the 'select' method. Bitwise 064 * closeness is determined by the {@link KeyAnalyzer} returning true or 065 * false for a bit being set or not in a given key. 066 * <p> 067 * This PATRICIA Trie supports both variable length and fixed length keys. 068 * Some methods, such as {@code getPrefixedBy(...)} are suited only to 069 * variable length keys, whereas {@code getPrefixedByBits(...)} is suited 070 * to fixed-size keys. 071 * <p> 072 * Additionally see <a 073 * href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/">PATRICIA</a> 074 * for more information. 075 * <p> 076 * Any methods here that take an {@code Object} may throw a 077 * {@code ClassCastException} if the method is expecting an instance of K 078 * (and it isn't K). 079 * 080 * <pre> 081 PatriciaTrie<String, String> trie = new PatriciaTrie<String, String> 082 (new CharSequenceKeyAnalyzer()); 083 084 trie.put("Lime", "Lime"); 085 trie.put("LimeWire", "LimeWire"); 086 trie.put("LimeRadio", "LimeRadio"); 087 trie.put("Lax", "Lax"); 088 trie.put("Lake", "Lake"); 089 trie.put("Lovely", "Lovely"); 090 091 System.out.println(trie.select("Lo")); 092 System.out.println(trie.select("Lime")); 093 094 System.out.println(trie.getPrefixedBy("La").toString()); 095 096 Output: 097 Lovely 098 Lime 099 {Lake=Lake, Lax=Lax} 100 101 * </pre> 102 * @author Roger Kapsi 103 * @author Sam Berlin 104 105 */ 106public class PatriciaTrie<K, V> extends AbstractMap<K, V> implements Trie<K, V>, Serializable { 107 108 private static final long serialVersionUID = 110232526181493307L; 109 110 /** Root element of the Trie. */ 111 private final TrieEntry<K, V> root = new TrieEntry<K, V>(null, null, -1); 112 113 /** Current size (total number of elements) of the Trie. */ 114 private int size = 0; 115 116 /** Number of times this has been modified (to fail-fast the iterators). */ 117 private transient int modCount = 0; 118 119 /** KeyAnalyzer used to analyze bit values of keys. */ 120 private final KeyAnalyzer<? super K> keyAnalyzer; 121 122 /** 123 * Constructs a new PatriciaTrie using the given keyAnalyzer. 124 * 125 * @param keyAnalyzer Used to analyze bit values of keys. 126 */ 127 public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) { 128 this.keyAnalyzer = keyAnalyzer; 129 } 130 131 /** 132 * Returns the KeyAnalyzer that constructed the trie. 133 * 134 * @return {@link #keyAnalyzer} 135 */ 136 public KeyAnalyzer<? super K> getKeyAnalyzer() { 137 return keyAnalyzer; 138 } 139 140 /** 141 * Returns the KeyAnalyzer as a comparator. 142 * 143 * @return Essentially just {@link #keyAnalyzer} casted as a 144 * {@link Comparator}. 145 */ 146 public Comparator<? super K> comparator() { 147 return keyAnalyzer; 148 } 149 150 /** 151 * Clears the Trie (i.e. removes all elements). 152 */ 153 public void clear() { 154 root.key = null; 155 root.bitIndex = -1; 156 root.value = null; 157 158 root.parent = null; 159 root.left = root; 160 root.right = null; 161 root.predecessor = root; 162 163 size = 0; 164 incrementModCount(); 165 } 166 167 /** 168 * Returns {@code true} if the Trie is empty. 169 * 170 * @return {@code true} if the trie is empty, {@code false} otherwise. 171 */ 172 public boolean isEmpty() { 173 return size == 0; 174 } 175 176 /** 177 * Returns the number items in the Trie. 178 * 179 * @return Items stored within trie. 180 */ 181 public int size() { 182 return size; 183 } 184 185 /** 186 * Increments both the size and mod counter. 187 */ 188 private void incrementSize() { 189 size++; 190 incrementModCount(); 191 } 192 193 /** 194 * Decrements the size and increments the mod counter. 195 */ 196 private void decrementSize() { 197 size--; 198 incrementModCount(); 199 } 200 201 /** Increments the mod counter. */ 202 private void incrementModCount() { 203 modCount++; 204 } 205 206 /** 207 * Adds a new {@code <key, value>} pair to the Trie and if a pair already 208 * exists it will be replaced. In the latter case it will return 209 * the old value. 210 */ 211 public V put(K key, V value) { 212 if (key == null) { 213 throw new NullPointerException("Key cannot be null"); 214 } 215 216 int keyLength = length(key); 217 218 // The only place to store a key with a length 219 // of zero bits is the root node 220 if (keyLength == 0) { 221 if (root.isEmpty()) { 222 incrementSize(); 223 } else { 224 incrementModCount(); 225 } 226 return root.setKeyValue(key, value); 227 } 228 229 TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength); 230 if (key.equals(found.key)) { 231 if (found.isEmpty()) { // <- must be the root 232 incrementSize(); 233 } else { 234 incrementModCount(); 235 } 236 return found.setKeyValue(key, value); 237 } 238 239 int bitIndex = bitIndex(key, found.key); 240 if (isValidBitIndex(bitIndex)) { // in 99.999...9% the case 241 /* NEW KEY+VALUE TUPLE */ 242 TrieEntry<K, V> t = new TrieEntry<K, V>(key, value, bitIndex); 243 addEntry(t, keyLength); 244 incrementSize(); 245 return null; 246 } else if (isNullBitKey(bitIndex)) { 247 // A bits of the Key are zero. The only place to 248 // store such a Key is the root Node! 249 250 /* NULL BIT KEY */ 251 if (root.isEmpty()) { 252 incrementSize(); 253 } else { 254 incrementModCount(); 255 } 256 return root.setKeyValue(key, value); 257 258 } else if (isEqualBitKey(bitIndex)) { 259 // This is a very special and rare case. 260 261 /* REPLACE OLD KEY+VALUE */ 262 if (found != root) { 263 incrementModCount(); 264 return found.setKeyValue(key, value); 265 } 266 } 267 268 throw new IndexOutOfBoundsException("Failed to put: " + key + " -> " + value + ", " + bitIndex); 269 } 270 271 /** 272 * Adds the given entry into the Trie. 273 * 274 * @param toAdd Trie entry to add. 275 * @param keyLength Length of the entry's key. 276 * 277 * @return Newly added trie entry. 278 */ 279 private TrieEntry<K, V> addEntry(TrieEntry<K, V> toAdd, int keyLength) { 280 TrieEntry<K, V> current = root.left; 281 TrieEntry<K, V> path = root; 282 while(true) { 283 if(current.bitIndex >= toAdd.bitIndex || current.bitIndex <= path.bitIndex) { 284 toAdd.predecessor = toAdd; 285 286 if (!isBitSet(toAdd.key, keyLength, toAdd.bitIndex)) { 287 toAdd.left = toAdd; 288 toAdd.right = current; 289 } else { 290 toAdd.left = current; 291 toAdd.right = toAdd; 292 } 293 294 toAdd.parent = path; 295 if (current.bitIndex >= toAdd.bitIndex) { 296 current.parent = toAdd; 297 } 298 299 // if we inserted an uplink, set the predecessor on it 300 if(current.bitIndex <= path.bitIndex) { 301 current.predecessor = toAdd; 302 } 303 304 if (path == root || !isBitSet(toAdd.key, keyLength, path.bitIndex)) 305 path.left = toAdd; 306 else 307 path.right = toAdd; 308 return toAdd; 309 } 310 311 path = current; 312 if(!isBitSet(toAdd.key, keyLength, current.bitIndex)) 313 current = current.left; 314 else 315 current = current.right; 316 } 317 } 318 319 @Override public Set<Map.Entry<K,V>> entrySet() { 320 Set<Map.Entry<K,V>> es = entrySet; 321 return (es != null ? es : (entrySet = new EntrySet())); 322 } 323 324 /** 325 * Attempt to find the given key within the trie. 326 * 327 * @param k Key to search for within the trie. 328 * 329 * @return Value whose Key equals our lookup Key or {@code null} if no 330 * such key exists. 331 */ 332 public V get(Object k) { 333 TrieEntry<K, V> entry = getEntry(k); 334 return entry != null ? entry.getValue() : null; 335 } 336 337 /** 338 * Returns the entry associated with the specified key in the 339 * PatriciaTrie. Returns null if the map contains no mapping 340 * for this key. 341 * 342 * This may throw ClassCastException if the object is not of type K. 343 * 344 * @param k Key to search for within the trie. 345 * 346 * @return Trie entry containing the given key and its associated value. 347 */ 348 TrieEntry<K,V> getEntry(Object k) { 349 K key = asKey(k); 350 if(key == null) 351 return null; 352 353 int keyLength = length(key); 354 TrieEntry<K,V> entry = getNearestEntryForKey(key, keyLength); 355 return !entry.isEmpty() && key.equals(entry.key) ? entry : null; 356 } 357 358 /** 359 * Gets the key as an object of type {@code K}. 360 * 361 * @param key Key to {@literal "cast"} to type {@code K}. 362 * 363 * @return Essentially {@code key} casted to type {@code K}. 364 */ 365 @SuppressWarnings("unchecked") 366 protected final K asKey(Object key) { 367 try { 368 return (K)key; 369 } catch(ClassCastException cce) { 370 // Because the type is erased, the cast & return are 371 // actually doing nothing, making this CCE impossible. 372 // However, it's still here on the off-chance it may 373 // work. 374 return null; 375 } 376 } 377 378 /** 379 * Returns the nearest entry for a given key. This is useful 380 * for finding knowing if a given key exists (and finding the value 381 * for it), or for inserting the key. 382 * 383 * The actual get implementation. This is very similar to 384 * selectR but with the exception that it might return the 385 * root Entry even if it's empty. 386 * 387 * @param key Key to search for within the trie. 388 * @param keyLength Length of {@code key}. 389 * 390 * @return Entry that is the closest match to the given {@code key}. 391 */ 392 private TrieEntry<K, V> getNearestEntryForKey(K key, int keyLength) { 393 TrieEntry<K, V> current = root.left; 394 TrieEntry<K, V> path = root; 395 while(true) { 396 if(current.bitIndex <= path.bitIndex) 397 return current; 398 399 path = current; 400 if(!isBitSet(key, keyLength, current.bitIndex)) 401 current = current.left; 402 else 403 current = current.right; 404 } 405 } 406 407 /** 408 * Returns the Value whose Key has the longest prefix 409 * in common with our lookup key. 410 * 411 * @param key Key to search for within the trie. 412 * 413 * @return Value associated with {@code key}. 414 */ 415 @SuppressWarnings("unchecked") 416 public V select(K key) { 417 int keyLength = length(key); 418 TrieEntry[] result = new TrieEntry[1]; 419 if (!selectR(root.left, -1, key, keyLength, result)) { 420 TrieEntry<K, V> e = result[0]; 421 return e.getValue(); 422 } 423 return null; 424 } 425 426 /** 427 * This is equivalent to the other selectR() method but without 428 * its overhead because we're selecting only one best matching 429 * Entry from the Trie. 430 * 431 * @param h Node representing root of subtree being searched. 432 * @param bitIndex 433 * @param key Key being matched. 434 * @param keyLength Length of {@code key}. 435 * @param result Array containing best match. 436 * 437 * @return Whether or not a node was selected. 438 */ 439 private boolean selectR(TrieEntry<K, V> h, int bitIndex, 440 final K key, final int keyLength, final TrieEntry[] result) { 441 442 if (h.bitIndex <= bitIndex) { 443 // If we hit the root Node and it is empty 444 // we have to look for an alternative best 445 // matching node. 446 if (!h.isEmpty()) { 447 result[0] = h; 448 return false; 449 } 450 return true; 451 } 452 453 if (!isBitSet(key, keyLength, h.bitIndex)) { 454 if (selectR(h.left, h.bitIndex, key, keyLength, result)) { 455 return selectR(h.right, h.bitIndex, key, keyLength, result); 456 } 457 } else { 458 if (selectR(h.right, h.bitIndex, key, keyLength, result)) { 459 return selectR(h.left, h.bitIndex, key, keyLength, result); 460 } 461 } 462 return false; 463 } 464 465 @SuppressWarnings("unchecked") 466 public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor) { 467 int keyLength = length(key); 468 TrieEntry[] result = new TrieEntry[]{ null }; 469 selectR(root.left, -1, key, keyLength, cursor, result); 470 return result[0]; 471 } 472 473 private boolean selectR(TrieEntry<K,V> h, int bitIndex, 474 final K key, 475 final int keyLength, 476 final Cursor<? super K, ? super V> cursor, 477 final TrieEntry[] result) { 478 479 if (h.bitIndex <= bitIndex) { 480 if(!h.isEmpty()) { 481 Cursor.SelectStatus ret = cursor.select(h); 482 switch(ret) { 483 case REMOVE: 484 throw new UnsupportedOperationException("cannot remove during select"); 485 case EXIT: 486 result[0] = h; 487 return false; // exit 488 case REMOVE_AND_EXIT: 489 TrieEntry<K, V> entry = new TrieEntry<K, V>(h.getKey(), h.getValue(), -1); 490 result[0] = entry; 491 removeEntry(h); 492 return false; 493 case CONTINUE: 494 // fall through. 495 } 496 } 497 return true; // continue 498 } 499 500 if (!isBitSet(key, keyLength, h.bitIndex)) { 501 if (selectR(h.left, h.bitIndex, key, keyLength, cursor, result)) { 502 return selectR(h.right, h.bitIndex, key, keyLength, cursor, result); 503 } 504 } else { 505 if (selectR(h.right, h.bitIndex, key, keyLength, cursor, result)) { 506 return selectR(h.left, h.bitIndex, key, keyLength, cursor, result); 507 } 508 } 509 510 return false; 511 } 512 513 /** 514 * Returns a view of this Trie of all elements that are 515 * prefixed by the given key. 516 * 517 * In a fixed-keysize Trie, this is essentially a 'get' operation. 518 * 519 * For example, if the trie contains 'Lime', 'LimeWire', 520 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then 521 * a lookup of 'Lime' would return 'Lime', 'LimeRadio', and 'LimeWire'. 522 * 523 * The view that this returns is optimized to have a very efficient 524 * Iterator. The {@link #firstKey()}, {@link #lastKey()}, and 525 * {@link #size()} methods must iterate over all possible values in order 526 * to determine the results. This information is cached until the Patricia 527 * tree changes. All other methods (except Iterator) must compare the 528 * given key to the prefix to ensure that it is within the range of 529 * the view. The Iterator's remove method must also relocate the subtree 530 * that contains the prefixes if the entry holding the subtree is removed 531 * or changes. Changing the subtree takes O(K) time. 532 * 533 * @param key Key to search for within the trie. 534 * 535 * @return {@code Map} containing keys matching the given prefix and their 536 * values. 537 */ 538 public SortedMap<K, V> getPrefixedBy(K key) { 539 return getPrefixedByBits(key, 0, keyAnalyzer.length(key)); 540 } 541 542 /** 543 * Returns a view of this Trie of all elements that are 544 * prefixed by the {@code length} of the {@code key}. 545 * 546 * Fixed-keysize Tries will not support this operation 547 * (because all keys will be the same length). 548 * 549 * For example, if the trie contains 'Lime', 'LimeWire', 550 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then 551 * a lookup of 'LimePlastics' with a length of 4 would 552 * return 'Lime', 'LimeRadio', and 'LimeWire'. 553 * 554 * The view that this returns is optimized to have a very efficient 555 * Iterator. The {@link #firstKey()}, {@link #lastKey()}, and 556 * {@link #size()} methods must iterate over all possible values in order 557 * to determine the results. This information is cached until the 558 * Patricia tree changes. All other methods (except Iterator) must 559 * compare the given key to the prefix to ensure that it is within the 560 * range of the view. The Iterator's remove method must also relocate the 561 * subtree that contains the prefixes if the entry holding the subtree is 562 * removed or changes. Changing the subtree takes O(K) time. 563 * 564 * @param key Key to search for within the trie. 565 * @param length Length of {@code key}. Ignored for tries with a fixed key 566 * size. 567 * 568 * @return {@code Map} containing keys matching the given prefix and their 569 * values. 570 */ 571 public SortedMap<K, V> getPrefixedBy(K key, int length) { 572 return getPrefixedByBits(key, 0, length * keyAnalyzer.bitsPerElement()); 573 } 574 575 /** 576 * Returns a view of this Trie of all elements that are prefixed 577 * by the {@code key}, starting at the given {@code offset} and for the 578 * given {@code length}. 579 * 580 * Fixed-keysize Tries will not support this operation 581 * (because all keys are the same length). 582 * 583 * For example, if the trie contains 'Lime', 'LimeWire', 584 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then 585 * a lookup of 'The Lime Plastics' with an offset of 4 and a 586 * length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'. 587 * 588 * The view that this returns is optimized to have a very efficient 589 * Iterator. The {@link #firstKey()}, {@link #lastKey()}, and 590 * {@link #size()} methods must iterate over all possible values in order 591 * to determine the results. This information is cached until the 592 * Patricia tree changes. All other methods (except Iterator) must 593 * compare the given key to the prefix to ensure that it is within the 594 * range of the view. The Iterator's remove method must also relocate the 595 * subtree that contains the prefixes if the entry holding the subtree is 596 * removed or changes. Changing the subtree takes O(K) time. 597 * 598 * @param key Key to search for within the trie. 599 * @param offset Offset to begin search at. 600 * @param length Length of {@code key}. Ignored for tries with a fixed key 601 * size. 602 * 603 * @return {@code Map} containing keys matching the given prefix and their 604 * values. 605 */ 606 public SortedMap<K, V> getPrefixedBy(K key, int offset, int length) { 607 return getPrefixedByBits(key, offset * keyAnalyzer.bitsPerElement(), length * keyAnalyzer.bitsPerElement()); 608 } 609 610 /** 611 * Returns a view of this Trie of all elements that are prefixed 612 * by the number of bits in the given {@code key}. 613 * 614 * Fixed-keysize Tries can support this operation as a way to do 615 * lookups of partial keys. That is, if the Trie is storing IP 616 * addresses, you can lookup all addresses that begin with 617 * '192.168' by providing the key '192.168.X.X' and a length of 16 618 * would return all addresses that begin with '192.168'. 619 * 620 * The view that this returns is optimized to have a very efficient 621 * Iterator. The {@link #firstKey()}, {@link #lastKey()}, and 622 * {@link #size()} methods must iterate over all possible values in order 623 * to determine the results. This information is cached until the Patricia 624 * tree changes. All other methods (except Iterator) must compare the 625 * given key to the prefix to ensure that it is within the range of the 626 * view. The Iterator's remove method must also relocate the subtree that 627 * contains the prefixes if the entry holding the subtree is removed or 628 * changes. Changing the subtree takes O(K) time. 629 * 630 * @param key Key to search for within the trie. 631 * @param bitLength Length of {@code key} in bits. 632 * 633 * @return {@code Map} containing keys matching the given prefix and their 634 * values. 635 */ 636 public SortedMap<K, V> getPrefixedByBits(K key, int bitLength) { 637 return getPrefixedByBits(key, 0, bitLength); 638 } 639 640 /** 641 * Returns a view of this map, with entries containing only those that 642 * are prefixed by a value whose bits matches the bits between 643 * {@code offset} and {@code length} in the given {@code key}. 644 * 645 * The view that this returns is optimized to have a very efficient 646 * Iterator. The {@link #firstKey()}, {@link #lastKey()}, and 647 * {@link #size()} methods must iterate over all possible values in order 648 * to determine the results. This information is cached until the 649 * Patricia tree changes. All other methods (except Iterator) must 650 * compare the given key to the prefix to ensure that it is within the 651 * range of the view. The Iterator's remove method must also relocate 652 * the subtree that contains the prefixes if the entry holding the 653 * subtree is removed or changes. Changing the subtree takes O(K) time. 654 * 655 * @param key Key to search for within the trie. 656 * @param offset Offset within key to begin search. 657 * @param length Length of {@code key} in bits. 658 * 659 * @return {@code Map} containing keys matching the given prefix and their 660 * values. 661 */ 662 private SortedMap<K, V> getPrefixedByBits(K key, int offset, int length) { 663 int offsetLength = offset + length; 664 if (offsetLength > length(key)) { 665 throw new IllegalArgumentException(offset + " + " + length + " > " + length(key)); 666 } 667 668 if(offsetLength == 0) 669 return this; 670 671 return new PrefixSubMap(key, offset, length); 672 } 673 674 /** 675 * Returns true if this trie contains the specified Key 676 * 677 * This may throw ClassCastException if the object is not 678 * of type K. 679 * 680 * @param k Key to search for within trie. 681 * 682 * @return {@code true} if the trie contains the given {@code k}. 683 */ 684 public boolean containsKey(Object k) { 685 K key = asKey(k); 686 if(key == null) 687 return false; 688 689 int keyLength = length(key); 690 TrieEntry entry = getNearestEntryForKey(key, keyLength); 691 return !entry.isEmpty() && key.equals(entry.key); 692 } 693 694 /** 695 * Returns true if this Trie contains the specified value. 696 * 697 * @param o Value to search for within trie. 698 * 699 * @return {@code true} if the trie contains something equal to {@code o}. 700 */ 701 public boolean containsValue(Object o) { 702 for(V v : values()) 703 if(valEquals(v, o)) 704 return true; 705 return false; 706 } 707 708 709 /** 710 * Removes a Key from the Trie if one exists 711 * 712 * This may throw ClassCastException if the object is not of type K. 713 * 714 * @param k Key to delete. 715 * 716 * @return Returns the deleted value. 717 */ 718 public V remove(Object k) { 719 K key = asKey(k); 720 if(key == null) 721 return null; 722 723 int keyLength = length(key); 724 TrieEntry<K, V> current = root.left; 725 TrieEntry<K, V> path = root; 726 while(true) { 727 if(current.bitIndex <= path.bitIndex) { 728 if(!current.isEmpty() && key.equals(current.key)) 729 return removeEntry(current); 730 else 731 return null; 732 } 733 734 path = current; 735 if(!isBitSet(key, keyLength, current.bitIndex)) 736 current = current.left; 737 else 738 current = current.right; 739 } 740 } 741 742 /** 743 * Removes a single entry from the Trie. 744 * 745 * If we found a Key (Entry h) then figure out if it's 746 * an internal (hard to remove) or external Entry (easy 747 * to remove) 748 * 749 * @param h Node to remove from the trie. 750 * 751 * @return Value that was removed from the trie. 752 */ 753 private V removeEntry(TrieEntry<K, V> h) { 754 if (h != root) { 755 if (h.isInternalNode()) { 756 removeInternalEntry(h); 757 } else { 758 removeExternalEntry(h); 759 } 760 } 761 762 decrementSize(); 763 return h.setKeyValue(null, null); 764 } 765 766 /** 767 * Removes an external entry from the Trie. 768 * 769 * If it's an external Entry then just remove it. 770 * This is very easy and straight forward. 771 * 772 * @param h Node to remove from the trie. 773 */ 774 private void removeExternalEntry(TrieEntry<K, V> h) { 775 if (h == root) { 776 throw new IllegalArgumentException("Cannot delete root Entry!"); 777 } else if (!h.isExternalNode()) { 778 throw new IllegalArgumentException(h + " is not an external Entry!"); 779 } 780 781 TrieEntry<K, V> parent = h.parent; 782 TrieEntry<K, V> child = (h.left == h) ? h.right : h.left; 783 784 if (parent.left == h) { 785 parent.left = child; 786 } else { 787 parent.right = child; 788 } 789 790 // either the parent is changing, or the predecessor is changing. 791 if (child.bitIndex > parent.bitIndex) { 792 child.parent = parent; 793 } else { 794 child.predecessor = parent; 795 } 796 797 } 798 799 /** 800 * Removes an internal entry from the Trie. 801 * 802 * If it's an internal Entry then "good luck" with understanding 803 * this code. The Idea is essentially that Entry p takes Entry h's 804 * place in the trie which requires some re-wiring. 805 * 806 * @param h Node to remove from the trie. 807 */ 808 private void removeInternalEntry(TrieEntry<K, V> h) { 809 if (h == root) { 810 throw new IllegalArgumentException("Cannot delete root Entry!"); 811 } else if (!h.isInternalNode()) { 812 throw new IllegalArgumentException(h + " is not an internal Entry!"); 813 } 814 815 TrieEntry<K, V> p = h.predecessor; 816 817 // Set P's bitIndex 818 p.bitIndex = h.bitIndex; 819 820 // Fix P's parent, predecessor and child Nodes 821 { 822 TrieEntry<K, V> parent = p.parent; 823 TrieEntry<K, V> child = (p.left == h) ? p.right : p.left; 824 825 // if it was looping to itself previously, 826 // it will now be pointed from it's parent 827 // (if we aren't removing it's parent -- 828 // in that case, it remains looping to itself). 829 // otherwise, it will continue to have the same 830 // predecessor. 831 if(p.predecessor == p && p.parent != h) 832 p.predecessor = p.parent; 833 834 if (parent.left == p) { 835 parent.left = child; 836 } else { 837 parent.right = child; 838 } 839 840 if (child.bitIndex > parent.bitIndex) { 841 child.parent = parent; 842 } 843 }; 844 845 // Fix H's parent and child Nodes 846 { 847 // If H is a parent of its left and right child 848 // then change them to P 849 if (h.left.parent == h) { 850 h.left.parent = p; 851 } 852 853 if (h.right.parent == h) { 854 h.right.parent = p; 855 } 856 857 // Change H's parent 858 if (h.parent.left == h) { 859 h.parent.left = p; 860 } else { 861 h.parent.right = p; 862 } 863 }; 864 865 // Copy the remaining fields from H to P 866 //p.bitIndex = h.bitIndex; 867 p.parent = h.parent; 868 p.left = h.left; 869 p.right = h.right; 870 871 // Make sure that if h was pointing to any uplinks, 872 // p now points to them. 873 if(isValidUplink(p.left, p)) 874 p.left.predecessor = p; 875 if(isValidUplink(p.right, p)) 876 p.right.predecessor = p; 877 878 } 879 880 /** 881 * Returns the node lexicographically before the given node (or null if none). 882 * 883 * This follows four simple branches: 884 * 885 * <pre> 886 * - If the uplink that returned us was a right uplink: 887 * - If predecessor's left is a valid uplink from predecessor, return it. 888 * - Else, follow the right path from the predecessor's left. 889 * - If the uplink that returned us was a left uplink: 890 * - Loop back through parents until we encounter a node where 891 * node != node.parent.left. 892 * - If node.parent.left is uplink from node.parent: 893 * - If node.parent.left is not root, return it. 894 * - If it is root & root isEmpty, return null. 895 * - If it is root & root !isEmpty, return root. 896 * - If node.parent.left is not uplink from node.parent: 897 * - Follow right path for first right child from node.parent.left 898 * </pre> 899 * 900 * @param start Node from which the search should begin. 901 * 902 * @return Node that is lexicographically {@literal "before"} {@code start}. 903 */ 904 private TrieEntry<K, V> previousEntry(TrieEntry<K, V> start) { 905 if(start.predecessor == null) 906 throw new IllegalArgumentException("must have come from somewhere!"); 907 908 if(start.predecessor.right == start) { 909 if(isValidUplink(start.predecessor.left, start.predecessor)) { 910 return start.predecessor.left; 911 } else { 912 return followRight(start.predecessor.left); 913 } 914 } else { 915 TrieEntry<K, V> node = start.predecessor; 916 while(node.parent != null && node == node.parent.left) 917 node = node.parent; 918 if(node.parent == null) // can be null if we're looking up root. 919 return null; 920 if(isValidUplink(node.parent.left, node.parent)) { 921 if(node.parent.left == root) { 922 if(root.isEmpty()) 923 return null; 924 else 925 return root; 926 } else { 927 return node.parent.left; 928 } 929 } else { 930 return followRight(node.parent.left); 931 } 932 } 933 } 934 935 /** 936 * Returns the entry lexicographically after the given entry. 937 * If the given entry is null, returns the first node. 938 * 939 * @param node Node whose subsequent entry is desired. 940 * 941 * @return Next lexicographic entry after the given {@code node}. 942 */ 943 private TrieEntry<K, V> nextEntry(TrieEntry<K, V> node) { 944 if(node == null) { 945 return firstEntry(); 946 } else { 947 return nextEntryImpl(node.predecessor, node, null); 948 } 949 } 950 951 /** 952 * Returns the entry lexicographically after the given entry. 953 * If the given entry is null, returns the first node. 954 * 955 * This will traverse only within the subtree. If the given node 956 * is not within the subtree, this will have undefined results. 957 * 958 * @param node Node whose subsequent entry is desired. 959 * @param parentOfSubtree Node that is parent of subtree being searched. 960 * 961 * @return Next lexicographic entry after the given {@code node}. 962 */ 963 private TrieEntry<K, V> nextEntryInSubtree(TrieEntry<K, V> node, TrieEntry<K, V> parentOfSubtree) { 964 if(node == null) { 965 return firstEntry(); 966 } else { 967 return nextEntryImpl(node.predecessor, node, parentOfSubtree); 968 } 969 } 970 971 /** 972 * Scans for the next node, starting at the specified point, and using 'previous' 973 * as a hint that the last node we returned was 'previous' (so we know not to return 974 * it again). If 'tree' is non-null, this will limit the search to the given tree. 975 * 976 * The basic premise is that each iteration can follow the following steps: 977 * 978 * 1) Scan all the way to the left. 979 * a) If we already started from this node last time, proceed to Step 2. 980 * b) If a valid uplink is found, use it. 981 * c) If the result is an empty node (root not set), break the scan. 982 * d) If we already returned the left node, break the scan. 983 * 984 * 2) Check the right. 985 * a) If we already returned the right node, proceed to Step 3. 986 * b) If it is a valid uplink, use it. 987 * c) Do Step 1 from the right node. 988 * 989 * 3) Back up through the parents until we encounter find a parent 990 * that we're not the right child of. 991 * 992 * 4) If there's no right child of that parent, the iteration is finished. 993 * Otherwise continue to Step 5. 994 * 995 * 5) Check to see if the right child is a valid uplink. 996 * a) If we already returned that child, proceed to Step 6. 997 * Otherwise, use it. 998 * 999 * 6) If the right child of the parent is the parent itself, we've 1000 * already found and returned the end of the Trie, so exit. 1001 * 1002 * 7) Do Step 1 on the parent's right child. 1003 * 1004 * @param start Node from which the search should begin. 1005 * @param previous Previously-searched node. 1006 * @param tree If not {@code null}, search will be limited to this subtree. 1007 * 1008 * @return Entry after {@code previous}. 1009 */ 1010 private TrieEntry<K, V> nextEntryImpl(TrieEntry<K, V> start, TrieEntry<K, V> previous, TrieEntry<K, V> tree) { 1011 TrieEntry<K, V> current = start; 1012 1013 // Only look at the left if this was a recursive or 1014 // the first check, otherwise we know we've already looked 1015 // at the left. 1016 if(previous == null || start != previous.predecessor) { 1017 while(!current.left.isEmpty()) { 1018 // stop traversing if we've already 1019 // returned the left of this node. 1020 if(previous == current.left) { 1021 break; 1022 } 1023 1024 if(isValidUplink(current.left, current)) { 1025 return current.left; 1026 } 1027 1028 current = current.left; 1029 } 1030 } 1031 1032 // If there's no data at all, exit. 1033 if(current.isEmpty()) { 1034 return null; 1035 } 1036 1037 // If we've already returned the left, 1038 // and the immediate right is null, 1039 // there's only one entry in the Trie 1040 // which is stored at the root. 1041 // 1042 // / ("") <-- root 1043 // \_/ \ 1044 // null <-- 'current' 1045 // 1046 if(current.right == null) 1047 return null; 1048 1049 // If nothing valid on the left, try the right. 1050 if(previous != current.right) { 1051 // See if it immediately is valid. 1052 if(isValidUplink(current.right, current)) { 1053 return current.right; 1054 } 1055 1056 // Must search on the right's side if it wasn't initially valid. 1057 return nextEntryImpl(current.right, previous, tree); 1058 } 1059 1060 // Neither left nor right are valid, find the first parent 1061 // whose child did not come from the right & traverse it. 1062 while(current == current.parent.right) { 1063 // If we're going to traverse to above the subtree, stop. 1064 if(current == tree) 1065 return null; 1066 1067 current = current.parent; 1068 } 1069 1070 // If we're on the top of the subtree, we can't go any higher. 1071 if(current == tree) 1072 return null; 1073 1074 1075 // If there's no right, the parent must be root, so we're done. 1076 if(current.parent.right == null) { 1077 return null; 1078 } 1079 1080 1081 // If the parent's right points to itself, we've found one. 1082 if(previous != current.parent.right && isValidUplink(current.parent.right, current.parent)) { 1083 return current.parent.right; 1084 } 1085 1086 // If the parent's right is itself, there can't be any more nodes. 1087 if(current.parent.right == current.parent) { 1088 return null; 1089 } 1090 1091 // We need to traverse down the parent's right's path. 1092 return nextEntryImpl(current.parent.right, previous, tree); 1093 } 1094 1095 /** Returns each entry as a string. */ 1096 public String toString() { 1097 StringBuilder buffer = new StringBuilder(); 1098 buffer.append("Trie[").append(size()).append("]={\n"); 1099 for(Iterator<Map.Entry<K, V>> i = newEntryIterator(); i.hasNext(); ) { 1100 buffer.append(" ").append(i.next().toString()).append("\n"); 1101 } 1102 buffer.append("}\n"); 1103 return buffer.toString(); 1104 } 1105 1106 public Map.Entry<K, V> traverse(Cursor<? super K, ? super V> cursor) { 1107 TrieEntry<K, V> entry = nextEntry(null); 1108 while(entry != null) { 1109 TrieEntry<K, V> current = entry; 1110 Cursor.SelectStatus ret = cursor.select(current); 1111 entry = nextEntry(current); 1112 switch(ret) { 1113 case EXIT: 1114 return current; 1115 case REMOVE: 1116 removeEntry(current); 1117 break; // out of switch, stay in while loop 1118 case REMOVE_AND_EXIT: 1119 Map.Entry<K, V> value = new TrieEntry<K, V>(current.getKey(), current.getValue(), -1); 1120 removeEntry(current); 1121 return value; 1122 case CONTINUE: // do nothing. 1123 } 1124 } 1125 1126 return null; 1127 } 1128 1129 /** 1130 * Returns true if 'next' is a valid uplink coming from 'from'. 1131 * 1132 * @param next 1133 * @param from 1134 * 1135 * @return {@code true} if {@code next} is a valid {@literal "uplink"} from 1136 * {@code from}. 1137 */ 1138 private boolean isValidUplink(TrieEntry<K, V> next, TrieEntry<K, V> from) { 1139 return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty(); 1140 } 1141 1142 /** 1143 * Returns true if bitIndex is a valid index. 1144 * 1145 * @param bitIndex Bit index to check. 1146 * 1147 * @return Whether or not the given {@code bitIndex} is valid. 1148 */ 1149 private static boolean isValidBitIndex(int bitIndex) { 1150 return 0 <= bitIndex && bitIndex <= Integer.MAX_VALUE; 1151 } 1152 1153 /** 1154 * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}. 1155 * 1156 * @param bitIndex 1157 * 1158 * @return 1159 */ 1160 private static boolean isNullBitKey(int bitIndex) { 1161 return bitIndex == KeyAnalyzer.NULL_BIT_KEY; 1162 } 1163 1164 /** 1165 * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}. 1166 * 1167 * @param bitIndex 1168 * 1169 * @return 1170 */ 1171 private static boolean isEqualBitKey(int bitIndex) { 1172 return bitIndex == KeyAnalyzer.EQUAL_BIT_KEY; 1173 } 1174 1175 /** 1176 * Returns the length of the key, or 0 if the key is null. 1177 * 1178 * @param key Key whose length is desired. {@code null} is allowed. 1179 * 1180 * @return Length of key. 1181 */ 1182 private int length(K key) { 1183 if (key == null) { 1184 return 0; 1185 } 1186 1187 return keyAnalyzer.length(key); 1188 } 1189 1190 /** 1191 * Returns whether or not the given bit on the key is set, or false if 1192 * the key is null. 1193 * 1194 * @param key Key to check. {@code null} is allowed. 1195 * @param keyLength Length of {@code key}. 1196 * @param bitIndex Bit index of {@code key} that should be checked. 1197 * 1198 * @return Whether or not the bit at {@code bitIndex} on {@code key} is 1199 * set. If {@code key} is {@code null}, {@code false} will be returned. 1200 */ 1201 private boolean isBitSet(K key, int keyLength, int bitIndex) { 1202 if (key == null) { // root's might be null! 1203 return false; 1204 } 1205 return keyAnalyzer.isBitSet(key, keyLength, bitIndex); 1206 } 1207 1208 /** 1209 * Utility method for calling 1210 * {@link KeyAnalyzer#bitIndex(Object, int, int, Object, int, int)}. 1211 * 1212 * @param key 1213 * @param foundKey 1214 * 1215 * @return 1216 */ 1217 private int bitIndex(K key, K foundKey) { 1218 return keyAnalyzer.bitIndex(key, 0, length(key), foundKey, 0, length(foundKey)); 1219 } 1220 1221 /** The actual Trie nodes. */ 1222 private static class TrieEntry<K,V> implements Map.Entry<K,V>, Serializable { 1223 1224 private static final long serialVersionUID = 4596023148184140013L; 1225 1226 private K key; 1227 private V value; 1228 1229 /** The index this entry is comparing. */ 1230 private int bitIndex; 1231 1232 /** The parent of this entry. */ 1233 private TrieEntry<K,V> parent; 1234 /** The left child of this entry. */ 1235 private TrieEntry<K,V> left; 1236 /** The right child of this entry. */ 1237 private TrieEntry<K,V> right; 1238 /** The entry who uplinks to this entry. */ 1239 private TrieEntry<K,V> predecessor; 1240 1241 private TrieEntry(K key, V value, int bitIndex) { 1242 this.key = key; 1243 this.value = value; 1244 1245 this.bitIndex = bitIndex; 1246 1247 this.parent = null; 1248 this.left = this; 1249 this.right = null; 1250 this.predecessor = this; 1251 } 1252 1253 public boolean equals(Object o) { 1254 if(o == this) { 1255 return true; 1256 } else if(o instanceof Map.Entry) { 1257 Map.Entry e = (Map.Entry)o; 1258 Object k1 = getKey(); 1259 Object k2 = e.getKey(); 1260 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 1261 Object v1 = getValue(); 1262 Object v2 = e.getValue(); 1263 if (v1 == v2 || (v1 != null && v1.equals(v2))) 1264 return true; 1265 } 1266 return false; 1267 } else { 1268 return false; 1269 } 1270 } 1271 1272 /** 1273 * Whether or not the entry is storing a key. 1274 * Only the root can potentially be empty, all other 1275 * nodes must have a key. 1276 */ 1277 public boolean isEmpty() { 1278 return key == null; 1279 } 1280 1281 public K getKey() { 1282 return key; 1283 } 1284 1285 public V getValue() { 1286 return value; 1287 } 1288 1289 public V setValue(V value) { 1290 V o = this.value; 1291 this.value = value; 1292 return o; 1293 } 1294 1295 /** 1296 * Replaces the old key and value with the new ones. 1297 * Returns the old vlaue. 1298 */ 1299 private V setKeyValue(K key, V value) { 1300 this.key = key; 1301 return setValue(value); 1302 } 1303 1304 /** Neither the left nor right child is a loopback */ 1305 private boolean isInternalNode() { 1306 return left != this && right != this; 1307 } 1308 1309 /** Either the left or right child is a loopback */ 1310 private boolean isExternalNode() { 1311 return !isInternalNode(); 1312 } 1313 1314 public String toString() { 1315 StringBuilder buffer = new StringBuilder(); 1316 1317 if (bitIndex == -1) { 1318 buffer.append("RootEntry("); 1319 } else { 1320 buffer.append("Entry("); 1321 } 1322 1323 buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], "); 1324 buffer.append("value=").append(getValue()).append(", "); 1325 //buffer.append("bitIndex=").append(bitIndex).append(", "); 1326 1327 if (parent != null) { 1328 if (parent.bitIndex == -1) { 1329 buffer.append("parent=").append("ROOT"); 1330 } else { 1331 buffer.append("parent=").append(parent.getKey()).append(" [").append(parent.bitIndex).append("]"); 1332 } 1333 } else { 1334 buffer.append("parent=").append("null"); 1335 } 1336 buffer.append(", "); 1337 1338 if (left != null) { 1339 if (left.bitIndex == -1) { 1340 buffer.append("left=").append("ROOT"); 1341 } else { 1342 buffer.append("left=").append(left.getKey()).append(" [").append(left.bitIndex).append("]"); 1343 } 1344 } else { 1345 buffer.append("left=").append("null"); 1346 } 1347 buffer.append(", "); 1348 1349 if (right != null) { 1350 if (right.bitIndex == -1) { 1351 buffer.append("right=").append("ROOT"); 1352 } else { 1353 buffer.append("right=").append(right.getKey()).append(" [").append(right.bitIndex).append("]"); 1354 } 1355 } else { 1356 buffer.append("right=").append("null"); 1357 } 1358 buffer.append(", "); 1359 1360 if(predecessor != null) { 1361 if(predecessor.bitIndex == -1) { 1362 buffer.append("predecessor=").append("ROOT"); 1363 } else { 1364 buffer.append("predecessor=").append(predecessor.getKey()).append(" [").append(predecessor.bitIndex).append("]"); 1365 } 1366 } 1367 1368 buffer.append(")"); 1369 return buffer.toString(); 1370 } 1371 } 1372 1373 /** 1374 * Defines the interface to analyze {@link Trie} keys on a bit 1375 * level. {@code KeyAnalyzer}'s 1376 * methods return the length of the key in bits, whether or not a bit is 1377 * set, and bits per element in the key. 1378 * <p> 1379 * Additionally, a method determines if a key is a prefix of another key and 1380 * returns the bit index where one key is different from another key (if 1381 * the key and found key are equal than the return value is EQUAL_BIT_KEY). 1382 * <p> 1383 * {@code KeyAnalyzer} defines: 1384 * <table summary="KeyAnalyzer definitions"> 1385 * <tr><td>NULL_BIT_KEY</td><td>When key's bits are all zero</td></tr> 1386 * <tr><td>EQUAL_BIT_KEY</td><td>When keys are the same </td></tr> 1387 * </table> 1388 */ 1389 public interface KeyAnalyzer<K> extends Comparator<K>, Serializable { 1390 1391 /** Returned by bitIndex if key's bits are all 0 */ 1392 int NULL_BIT_KEY = -1; 1393 1394 /** 1395 * Returned by bitIndex if key and found key are 1396 * equal. This is a very very specific case and 1397 * shouldn't happen on a regular basis 1398 */ 1399 int EQUAL_BIT_KEY = -2; 1400 1401 /** 1402 * Returns the length of the Key in bits. 1403 * 1404 * @param key Key whose length should be computed. 1405 * 1406 * @return Length of {@code key}. 1407 */ 1408 int length(K key); 1409 1410 /** 1411 * Returns whether or not a bit is set 1412 * 1413 * @param key 1414 * @param keyLength 1415 * @param bitIndex 1416 */ 1417 boolean isBitSet(K key, int keyLength, int bitIndex); 1418 1419 /** 1420 * Returns the n-th different bit between key and found. 1421 * This starts the comparison in key at 'keyStart' and goes 1422 * for 'keyLength' bits, and compares to the found key 1423 * starting at 'foundStart' and going for 'foundLength' bits. 1424 * 1425 * @param key 1426 * @param keyStart 1427 * @param keyLength 1428 * @param found 1429 * @param foundStart 1430 * @param foundLength 1431 * 1432 * @return 1433 */ 1434 int bitIndex(K key, int keyStart, int keyLength, 1435 K found, int foundStart, int foundLength); 1436 1437 /** 1438 * Returns the number of bits per element in the key. 1439 * This is only useful for variable-length keys, such as Strings. 1440 * 1441 * @return Bits per key element. 1442 */ 1443 int bitsPerElement(); 1444 1445 /** 1446 * Determines whether or not the given prefix (from offset to length) 1447 * is a prefix of the given key. 1448 * 1449 * @return {@code true} if {@code prefix} matches the given 1450 * {@code offset} start and {@code length} for {@code key}. 1451 */ 1452 boolean isPrefix(K prefix, int offset, int length, K key); 1453 } 1454 1455 /** An iterator that stores a single TrieEntry. */ 1456 private class SingletonIterator implements Iterator<Map.Entry<K, V>> { 1457 private final TrieEntry<K, V> entry; 1458 private int hit = 0; 1459 1460 public SingletonIterator(TrieEntry<K, V> entry) { 1461 this.entry = entry; 1462 } 1463 1464 public boolean hasNext() { 1465 return hit == 0; 1466 } 1467 1468 public Map.Entry<K, V> next() { 1469 if(hit != 0) 1470 throw new NoSuchElementException(); 1471 hit++; 1472 return entry; 1473 } 1474 1475 public void remove() { 1476 if(hit != 1) 1477 throw new IllegalStateException(); 1478 hit++; 1479 PatriciaTrie.this.removeEntry(entry); 1480 } 1481 1482 } 1483 1484 /** An iterator for the entries. */ 1485 private abstract class NodeIterator<E> implements Iterator<E> { 1486 protected int expectedModCount = modCount; // For fast-fail 1487 protected TrieEntry<K, V> next; // the next node to return 1488 protected TrieEntry<K, V> current; // the current entry we're on 1489 1490 // Starts iteration from the beginning. 1491 protected NodeIterator() { 1492 next = PatriciaTrie.this.nextEntry(null); 1493 } 1494 1495 // Starts iteration at the given entry. 1496 protected NodeIterator(TrieEntry<K, V> firstEntry) { 1497 next = firstEntry; 1498 } 1499 1500 public boolean hasNext() { 1501 return next != null; 1502 } 1503 1504 TrieEntry<K,V> nextEntry() { 1505 if (modCount != expectedModCount) 1506 throw new ConcurrentModificationException(); 1507 TrieEntry<K,V> e = next; 1508 if (e == null) 1509 throw new NoSuchElementException(); 1510 1511 next = findNext(e); 1512 current = e; 1513 return e; 1514 } 1515 1516 protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior) { 1517 return PatriciaTrie.this.nextEntry(prior); 1518 } 1519 1520 public void remove() { 1521 if (current == null) 1522 throw new IllegalStateException(); 1523 if (modCount != expectedModCount) 1524 throw new ConcurrentModificationException(); 1525 1526 TrieEntry<K, V> node = current; 1527 current = null; 1528 PatriciaTrie.this.removeEntry(node); 1529 1530 expectedModCount = modCount; 1531 } 1532 } 1533 1534 private class ValueIterator extends NodeIterator<V> { 1535 public V next() { 1536 return nextEntry().value; 1537 } 1538 } 1539 1540 private class KeyIterator extends NodeIterator<K> { 1541 public K next() { 1542 return nextEntry().getKey(); 1543 } 1544 } 1545 1546 private class EntryIterator extends NodeIterator<Map.Entry<K,V>> { 1547 public Map.Entry<K,V> next() { 1548 return nextEntry(); 1549 } 1550 } 1551 1552 /** An iterator for iterating over a prefix search. */ 1553 private class PrefixEntryIterator extends NodeIterator<Map.Entry<K, V>> { 1554 // values to reset the subtree if we remove it. 1555 protected final K prefix; 1556 protected final int offset; 1557 protected final int length; 1558 protected boolean lastOne; 1559 1560 protected TrieEntry<K, V> subtree; // the subtree to search within 1561 1562 // Starts iteration at the given entry & search only within the given subtree. 1563 PrefixEntryIterator(TrieEntry<K, V> startScan, K prefix, int offset, int length) { 1564 subtree = startScan; 1565 next = PatriciaTrie.this.followLeft(startScan); 1566 this.prefix = prefix; 1567 this.offset = offset; 1568 this.length = length; 1569 } 1570 1571 public Map.Entry<K,V> next() { 1572 Map.Entry<K, V> entry = nextEntry(); 1573 if(lastOne) 1574 next = null; 1575 return entry; 1576 } 1577 1578 @Override 1579 protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior) { 1580 return PatriciaTrie.this.nextEntryInSubtree(prior, subtree); 1581 } 1582 1583 @Override 1584 public void remove() { 1585 // If the current entry we're removing is the subtree 1586 // then we need to find a new subtree parent. 1587 boolean needsFixing = false; 1588 int bitIdx = subtree.bitIndex; 1589 if(current == subtree) 1590 needsFixing = true; 1591 1592 super.remove(); 1593 1594 // If the subtree changed its bitIndex or we 1595 // removed the old subtree, get a new one. 1596 if(bitIdx != subtree.bitIndex || needsFixing) 1597 subtree = subtree(prefix, offset, length); 1598 1599 // If the subtree's bitIndex is less than the 1600 // length of our prefix, it's the last item 1601 // in the prefix tree. 1602 if(length >= subtree.bitIndex) 1603 lastOne = true; 1604 } 1605 1606 } 1607 1608 /** An iterator for submaps. */ 1609 private class SubMapEntryIterator extends NodeIterator<Map.Entry<K,V>> { 1610 private final K firstExcludedKey; 1611 1612 SubMapEntryIterator(TrieEntry<K,V> first, TrieEntry<K,V> firstExcluded) { 1613 super(first); 1614 firstExcludedKey = 1615 (firstExcluded == null ? null : firstExcluded.key); 1616 } 1617 1618 public boolean hasNext() { 1619 return next != null && next.key != firstExcludedKey; 1620 } 1621 1622 public Map.Entry<K,V> next() { 1623 if (next == null || next.key == firstExcludedKey) 1624 throw new NoSuchElementException(); 1625 return nextEntry(); 1626 } 1627 } 1628 1629 Iterator<K> newKeyIterator() { 1630 return new KeyIterator(); 1631 } 1632 1633 Iterator<V> newValueIterator() { 1634 return new ValueIterator(); 1635 } 1636 1637 Iterator<Map.Entry<K,V>> newEntryIterator() { 1638 return new EntryIterator(); 1639 } 1640 1641 /** 1642 * Each of these fields are initialized to contain an instance of the 1643 * appropriate view the first time this view is requested. The views are 1644 * stateless, so there's no reason to create more than one of each. 1645 */ 1646 private transient volatile Set<K> keySet = null; 1647 private transient volatile Collection<V> values = null; 1648 private transient volatile Set<Map.Entry<K,V>> entrySet = null; 1649 1650 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 1651 public Iterator<Map.Entry<K,V>> iterator() { 1652 return newEntryIterator(); 1653 } 1654 1655 public boolean contains(Object o) { 1656 if (!(o instanceof Map.Entry)) 1657 return false; 1658 1659 TrieEntry<K,V> candidate = getEntry(((Map.Entry)o).getKey()); 1660 return candidate != null && candidate.equals(o); 1661 } 1662 1663 public boolean remove(Object o) { 1664 int size = size(); 1665 PatriciaTrie.this.remove(o); 1666 return size != size(); 1667 } 1668 1669 public int size() { 1670 return size; 1671 } 1672 1673 public void clear() { 1674 PatriciaTrie.this.clear(); 1675 } 1676 } 1677 1678 /** 1679 * Returns a set view of the keys contained in this map. The set is 1680 * backed by the map, so changes to the map are reflected in the set, and 1681 * vice-versa. The set supports element removal, which removes the 1682 * corresponding mapping from this map, via the {@code Iterator.remove}, 1683 * {@code Set.remove}, {@code removeAll}, {@code retainAll}, and 1684 * {@code clear} operations. It does not support the {@code add} or 1685 * {@code addAll} operations. 1686 * 1687 * @return a set view of the keys contained in this map. 1688 */ 1689 public Set<K> keySet() { 1690 Set<K> ks = keySet; 1691 return (ks != null ? ks : (keySet = new KeySet())); 1692 } 1693 1694 private class KeySet extends AbstractSet<K> { 1695 public Iterator<K> iterator() { 1696 return newKeyIterator(); 1697 } 1698 public int size() { 1699 return size; 1700 } 1701 public boolean contains(Object o) { 1702 return containsKey(o); 1703 } 1704 public boolean remove(Object o) { 1705 int size = size(); 1706 PatriciaTrie.this.remove(o); 1707 return size != size(); 1708 } 1709 public void clear() { 1710 PatriciaTrie.this.clear(); 1711 } 1712 } 1713 1714 /** 1715 * Returns a collection view of the values contained in this map. The 1716 * collection is backed by the map, so changes to the map are reflected in 1717 * the collection, and vice-versa. The collection supports element 1718 * removal, which removes the corresponding mapping from this map, via the 1719 * {@code Iterator.remove}, {@code Collection.remove}, 1720 * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 1721 * It does not support the {@code add} or {@code addAll} operations. 1722 * 1723 * @return a collection view of the values contained in this map. 1724 */ 1725 public Collection<V> values() { 1726 Collection<V> vs = values; 1727 return (vs != null ? vs : (values = new Values())); 1728 } 1729 1730 /** Test two values for equality. Works with null values. */ 1731 private static boolean valEquals(Object o1, Object o2) { 1732 return (o1==null ? o2==null : o1.equals(o2)); 1733 } 1734 1735 private class Values extends AbstractCollection<V> { 1736 public Iterator<V> iterator() { 1737 return newValueIterator(); 1738 } 1739 public int size() { 1740 return size; 1741 } 1742 public boolean contains(Object o) { 1743 return containsValue(o); 1744 } 1745 public void clear() { 1746 PatriciaTrie.this.clear(); 1747 } 1748 public boolean remove(Object o) { 1749 for(Iterator<V> i = iterator(); i.hasNext(); ) { 1750 V v = i.next(); 1751 if(valEquals(v, o)) { 1752 i.remove(); 1753 return true; 1754 } 1755 } 1756 return false; 1757 } 1758 } 1759 1760 /** 1761 * Returns the first entry the Trie is storing. 1762 * 1763 * This is implemented by going always to the left until 1764 * we encounter a valid uplink. That uplink is the first key. 1765 */ 1766 private TrieEntry<K, V> firstEntry() { 1767 // if Trie is empty, no first node. 1768 if(isEmpty()) 1769 return null; 1770 1771 return followLeft(root); 1772 } 1773 1774 /** Goes left through the tree until it finds a valid node. */ 1775 private TrieEntry<K, V> followLeft(TrieEntry<K, V> node) { 1776 while(true) { 1777 TrieEntry<K, V> child = node.left; 1778 // if we hit root and it didn't have a node, go right instead. 1779 if(child.isEmpty()) 1780 child = node.right; 1781 1782 if(child.bitIndex <= node.bitIndex) 1783 return child; 1784 1785 node = child; 1786 } 1787 } 1788 1789 /** 1790 * Returns the last entry the Trie is storing. 1791 * <p> 1792 * This is implemented by going always to the right until 1793 * we encounter a valid uplink. That uplink is the last key. 1794 */ 1795 private TrieEntry<K, V> lastEntry() { 1796 return followRight(root.left); 1797 } 1798 1799 /** Traverses down the right path until it finds an uplink. */ 1800 protected TrieEntry<K, V> followRight(TrieEntry<K, V> node) { 1801 // if Trie is empty, no last entry. 1802 if(node.right == null) 1803 return null; 1804 1805 // Go as far right as possible, until we encounter an uplink. 1806 while(node.right.bitIndex > node.bitIndex) 1807 node = node.right; 1808 1809 return node.right; 1810 } 1811 1812 public K firstKey() { 1813 return firstEntry().getKey(); 1814 } 1815 1816 public SortedMap<K, V> headMap(K toKey) { 1817 return new SubMap(null, toKey); 1818 } 1819 1820 public K lastKey() { 1821 TrieEntry<K, V> entry = lastEntry(); 1822 if(entry != null) 1823 return entry.getKey(); 1824 else 1825 return null; 1826 } 1827 1828 1829 public SortedMap<K, V> subMap(K fromKey, K toKey) { 1830 return new SubMap(fromKey, toKey); 1831 } 1832 1833 public SortedMap<K, V> tailMap(K fromKey) { 1834 return new SubMap(fromKey, null); 1835 } 1836 1837 /** 1838 * Returns an entry strictly higher than the given key, 1839 * or null if no such entry exists. 1840 * 1841 * @param key 1842 * 1843 * @return 1844 */ 1845 protected TrieEntry<K,V> higherEntry(K key) { 1846 // TODO: Cleanup so that we don't actually have to add/remove from the 1847 // tree. (We do it here because there are other well-defined 1848 // functions to perform the search.) 1849 int keyLength = length(key); 1850 1851 if (keyLength == 0) { 1852 if(!root.isEmpty()) { 1853 // If data in root, and more after -- return it. 1854 if(size() > 1) { 1855 return nextEntry(root); 1856 } else { // If no more after, no higher entry. 1857 return null; 1858 } 1859 } else { 1860 // Root is empty & we want something after empty, return first. 1861 return firstEntry(); 1862 } 1863 } 1864 1865 TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength); 1866 if (key.equals(found.key)) 1867 return nextEntry(found); 1868 1869 int bitIndex = bitIndex(key, found.key); 1870 if (isValidBitIndex(bitIndex)) { 1871 TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex); 1872 addEntry(added, keyLength); 1873 incrementSize(); // must increment because remove will decrement 1874 TrieEntry<K, V> ceil = nextEntry(added); 1875 removeEntry(added); 1876 modCount -= 2; // we didn't really modify it. 1877 return ceil; 1878 } else if (isNullBitKey(bitIndex)) { 1879 if (!root.isEmpty()) 1880 return firstEntry(); 1881 else if(size() > 1) 1882 return nextEntry(firstEntry()); 1883 else 1884 return null; 1885 } else if (isEqualBitKey(bitIndex)) { 1886 return nextEntry(found); 1887 } 1888 1889 // we should have exited above. 1890 throw new IllegalStateException("invalid lookup: " + key); 1891 } 1892 1893 /** 1894 * Returns a key-value mapping associated with the least key greater 1895 * than or equal to the given key, or null if there is no such key. 1896 * 1897 * @param key 1898 * 1899 * @return 1900 */ 1901 protected TrieEntry<K,V> ceilingEntry(K key) { 1902 // Basically: 1903 // Follow the steps of adding an entry, but instead... 1904 // 1905 // - If we ever encounter a situation where we found an equal 1906 // key, we return it immediately. 1907 // 1908 // - If we hit an empty root, return the first iterable item. 1909 // 1910 // - If we have to add a new item, we temporarily add it, 1911 // find the successor to it, then remove the added item. 1912 // 1913 // These steps ensure that the returned value is either the 1914 // entry for the key itself, or the first entry directly after 1915 // the key. 1916 1917 // TODO: Cleanup so that we don't actually have to add/remove from the 1918 // tree. (We do it here because there are other well-defined 1919 // functions to perform the search.) 1920 int keyLength = length(key); 1921 1922 if (keyLength == 0) { 1923 if(!root.isEmpty()) 1924 return root; 1925 else 1926 return firstEntry(); 1927 } 1928 1929 TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength); 1930 if (key.equals(found.key)) 1931 return found; 1932 1933 int bitIndex = bitIndex(key, found.key); 1934 if (isValidBitIndex(bitIndex)) { 1935 TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex); 1936 addEntry(added, keyLength); 1937 incrementSize(); // must increment because remove will decrement 1938 TrieEntry<K, V> ceil = nextEntry(added); 1939 removeEntry(added); 1940 modCount -= 2; // we didn't really modify it. 1941 return ceil; 1942 } else if (isNullBitKey(bitIndex)) { 1943 if (!root.isEmpty()) 1944 return root; 1945 else 1946 return firstEntry(); 1947 } else if (isEqualBitKey(bitIndex)) { 1948 return found; 1949 } 1950 1951 // we should have exited above. 1952 throw new IllegalStateException("invalid lookup: " + key); 1953 } 1954 1955 /** 1956 * Returns a key-value mapping associated with the greatest key 1957 * strictly less than the given key, or null if there is no such key. 1958 * 1959 * @param key 1960 * 1961 * @return 1962 */ 1963 protected TrieEntry<K,V> lowerEntry(K key) { 1964 // Basically: 1965 // Follow the steps of adding an entry, but instead... 1966 // 1967 // - If we ever encounter a situation where we found an equal 1968 // key, we return it's previousEntry immediately. 1969 // 1970 // - If we hit root (empty or not), return null. 1971 // 1972 // - If we have to add a new item, we temporarily add it, 1973 // find the previousEntry to it, then remove the added item. 1974 // 1975 // These steps ensure that the returned value is always just before 1976 // the key or null (if there was nothing before it). 1977 1978 // TODO: Cleanup so that we don't actually have to add/remove from the 1979 // tree. (We do it here because there are other well-defined 1980 // functions to perform the search.) 1981 int keyLength = length(key); 1982 1983 if (keyLength == 0) { 1984 return null; // there can never be anything before root. 1985 } 1986 1987 TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength); 1988 if (key.equals(found.key)) 1989 return previousEntry(found); 1990 1991 int bitIndex = bitIndex(key, found.key); 1992 if (isValidBitIndex(bitIndex)) { 1993 TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex); 1994 addEntry(added, keyLength); 1995 incrementSize(); // must increment because remove will decrement 1996 TrieEntry<K, V> prior = previousEntry(added); 1997 removeEntry(added); 1998 modCount -= 2; // we didn't really modify it. 1999 return prior; 2000 } else if (isNullBitKey(bitIndex)) { 2001 return null; 2002 } else if (isEqualBitKey(bitIndex)) { 2003 return previousEntry(found); 2004 } 2005 2006 // we should have exited above. 2007 throw new IllegalStateException("invalid lookup: " + key); 2008 } 2009 2010 /** 2011 * Returns a key-value mapping associated with the greatest key 2012 * less than or equal to the given key, or null if there is no such key. 2013 * 2014 * @param key 2015 * 2016 * @return 2017 */ 2018 protected TrieEntry<K,V> floorEntry(K key) { 2019 // TODO: Cleanup so that we don't actually have to add/remove from the 2020 // tree. (We do it here because there are other well-defined 2021 // functions to perform the search.) 2022 int keyLength = length(key); 2023 2024 if (keyLength == 0) { 2025 if(!root.isEmpty()) 2026 return root; 2027 else 2028 return null; 2029 } 2030 2031 TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength); 2032 if (key.equals(found.key)) 2033 return found; 2034 2035 int bitIndex = bitIndex(key, found.key); 2036 if (isValidBitIndex(bitIndex)) { 2037 TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex); 2038 addEntry(added, keyLength); 2039 incrementSize(); // must increment because remove will decrement 2040 TrieEntry<K, V> floor = previousEntry(added); 2041 removeEntry(added); 2042 modCount -= 2; // we didn't really modify it. 2043 return floor; 2044 } else if (isNullBitKey(bitIndex)) { 2045 if (!root.isEmpty()) 2046 return root; 2047 else 2048 return null; 2049 } else if (isEqualBitKey(bitIndex)) { 2050 return found; 2051 } 2052 2053 // we should have exited above. 2054 throw new IllegalStateException("invalid lookup: " + key); 2055 } 2056 2057 2058 /** 2059 * Finds the subtree that contains the prefix. 2060 * 2061 * This is very similar to getR but with the difference that 2062 * we stop the lookup if h.bitIndex > keyLength. 2063 * 2064 * @param prefix 2065 * @param offset 2066 * @param length 2067 * 2068 * @return 2069 */ 2070 private TrieEntry<K, V> subtree(K prefix, int offset, int length) { 2071 TrieEntry<K, V> current = root.left; 2072 TrieEntry<K, V> path = root; 2073 while(true) { 2074 if(current.bitIndex <= path.bitIndex || length < current.bitIndex) 2075 break; 2076 2077 path = current; 2078 if(!isBitSet(prefix, length+offset, current.bitIndex+offset)) { 2079 current = current.left; 2080 } else { 2081 current = current.right; 2082 } 2083 } 2084 2085 // Make sure the entry is valid for a subtree. 2086 TrieEntry<K, V> entry = current.isEmpty() ? path : current; 2087 2088 // If entry is root, it can't be empty. 2089 if (entry.isEmpty()) 2090 return null; 2091 2092 int offsetLength = offset + length; 2093 2094 // if root && length of root is less than length of lookup, 2095 // there's nothing. 2096 // (this prevents returning the whole subtree if root has an empty 2097 // string and we want to lookup things with "\0") 2098 if(entry == root && length(entry.getKey()) < offsetLength) 2099 return null; 2100 2101 // Found key's length-th bit differs from our key 2102 // which means it cannot be the prefix... 2103 if(isBitSet(prefix, offsetLength, offsetLength) != 2104 isBitSet(entry.key, length(entry.key), length)) { 2105 return null; 2106 } 2107 2108 // ... or there are less than 'length' equal bits 2109 int bitIndex = keyAnalyzer.bitIndex(prefix, offset, length, 2110 entry.key, 0, length(entry.getKey())); 2111 if (bitIndex >= 0 && bitIndex < length) 2112 return null; 2113 2114 return entry; 2115 } 2116 2117 /** A submap used for prefix views over the Trie. */ 2118 private class PrefixSubMap extends SubMap { 2119 protected final K prefix; 2120 protected final int offset; 2121 protected final int length; 2122 private transient int keyModCount = 0; 2123 protected int size; 2124 2125 PrefixSubMap(K prefix, int offset, int length) { 2126 this.prefix = prefix; 2127 this.offset = offset; 2128 this.length = length; 2129 fromInclusive = false; 2130 } 2131 2132 public K firstKey() { 2133 fixup(); 2134 TrieEntry<K,V> e; 2135 if(fromKey == null) { 2136 e = firstEntry(); 2137 } else { 2138 e = higherEntry(fromKey); 2139 } 2140 2141 K first = e != null ? e.getKey() : null; 2142 if (e == null || !keyAnalyzer.isPrefix(prefix, offset, length, first)) 2143 throw new NoSuchElementException(); 2144 return first; 2145 } 2146 2147 public K lastKey() { 2148 fixup(); 2149 TrieEntry<K,V> e; 2150 if(toKey == null) { 2151 e = lastEntry(); 2152 } else { 2153 e = lowerEntry(toKey); 2154 } 2155 2156 K last = e != null ? e.getKey() : null; 2157 if (e == null || !keyAnalyzer.isPrefix(prefix, offset, length, last)) 2158 throw new NoSuchElementException(); 2159 return last; 2160 } 2161 2162 protected boolean inRange(K key) { 2163 return keyAnalyzer.isPrefix(prefix, offset, length, key); 2164 } 2165 2166 protected boolean inRange2(K key) { 2167 return keyAnalyzer.isPrefix(prefix, offset, length, key); 2168 } 2169 2170 protected boolean inToRange(K key, boolean forceInclusive) { 2171 return keyAnalyzer.isPrefix(prefix, offset, length, key); 2172 } 2173 2174 protected boolean inFromRange(K key, boolean forceInclusive) { 2175 return keyAnalyzer.isPrefix(prefix, offset, length, key); 2176 } 2177 2178 private void fixup() { 2179 // The trie has changed since we last 2180 // found our toKey / fromKey 2181 if(modCount != keyModCount) { 2182 Iterator<Map.Entry<K, V>> iter = entrySet().iterator(); 2183 size = 0; 2184 2185 Map.Entry<K, V> entry = null; 2186 if(iter.hasNext()) { 2187 entry = iter.next(); 2188 size = 1; 2189 } 2190 2191 fromKey = entry == null ? null : entry.getKey(); 2192 if(fromKey != null) { 2193 TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry); 2194 fromKey = prior == null ? null : prior.getKey(); 2195 } 2196 2197 toKey = fromKey; 2198 2199 while(iter.hasNext()) { 2200 size++; 2201 entry = iter.next(); 2202 } 2203 2204 toKey = entry == null ? null : entry.getKey(); 2205 2206 if(toKey != null) { 2207 entry = nextEntry((TrieEntry<K, V>)entry); 2208 toKey = entry == null ? null : entry.getKey(); 2209 } 2210 2211 keyModCount = modCount; 2212 } 2213 } 2214 2215 protected Set<Map.Entry<K, V>> newSubMapEntrySet() { 2216 return new PrefixEntrySetView(); 2217 } 2218 2219 private class PrefixEntrySetView extends SubMap.EntrySetView { 2220 private TrieEntry<K, V> prefixStart; 2221 private int iterModCount = 0; 2222 2223 public int size() { 2224 fixup(); 2225 return PrefixSubMap.this.size; 2226 } 2227 2228 @SuppressWarnings("unchecked") 2229 public Iterator<Map.Entry<K,V>> iterator() { 2230 if(modCount != iterModCount) { 2231 prefixStart = subtree(prefix, offset, length); 2232 iterModCount = modCount; 2233 } 2234 2235 if(prefixStart == null) { 2236 return new EmptyIterator(); 2237 } else if(length >= prefixStart.bitIndex){ 2238 return new SingletonIterator(prefixStart); 2239 } else { 2240 return new PrefixEntryIterator(prefixStart, prefix, offset, length); 2241 } 2242 } 2243 } 2244 } 2245 2246 private class SubMap extends AbstractMap<K,V> implements SortedMap<K,V>, java.io.Serializable { 2247 2248 // TODO: add serialVersionUID 2249 2250 /** The key to start from, null if the beginning. */ 2251 protected K fromKey; 2252 2253 /** The key to end at, null if till the end. */ 2254 protected K toKey; 2255 2256 /** Whether or not the 'from' is inclusive. */ 2257 protected boolean fromInclusive; 2258 2259 /** Whether or not the 'to' is inclusive. */ 2260 protected boolean toInclusive; 2261 2262 /** 2263 * Constructs a blank SubMap -- this should ONLY be used 2264 * by subclasses that wish to lazily construct their 2265 * fromKey or toKey 2266 */ 2267 protected SubMap() {} 2268 2269 SubMap(K fromKey, K toKey) { 2270 if(fromKey == null && toKey == null) 2271 throw new IllegalArgumentException("must have a from or to!"); 2272 if(fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0) 2273 throw new IllegalArgumentException("fromKey > toKey"); 2274 this.fromKey = fromKey; 2275 this.toKey = toKey; 2276 fromInclusive = true; 2277 } 2278 2279 public boolean isEmpty() { 2280 return entrySet().isEmpty(); 2281 } 2282 2283 @SuppressWarnings("unchecked") 2284 public boolean containsKey(Object key) { 2285 return inRange((K) key) && PatriciaTrie.this.containsKey(key); 2286 } 2287 2288 @SuppressWarnings("unchecked") 2289 public V remove(Object key) { 2290 if(!inRange((K)key)) 2291 return null; 2292 return PatriciaTrie.this.remove(key); 2293 } 2294 2295 @SuppressWarnings("unchecked") 2296 public V get(Object key) { 2297 if (!inRange((K) key)) 2298 return null; 2299 return PatriciaTrie.this.get(key); 2300 } 2301 2302 public V put(K key, V value) { 2303 if (!inRange(key)) 2304 throw new IllegalArgumentException("key out of range"); 2305 return PatriciaTrie.this.put(key, value); 2306 } 2307 2308 public Comparator<? super K> comparator() { 2309 return keyAnalyzer; 2310 } 2311 2312 public K firstKey() { 2313 TrieEntry<K,V> e; 2314 if(fromKey == null) { 2315 e = firstEntry(); 2316 } else { 2317 if(fromInclusive) 2318 e = ceilingEntry(fromKey); 2319 else 2320 e = higherEntry(fromKey); 2321 } 2322 2323 K first = e != null ? e.getKey() : null; 2324 if (e == null || toKey != null && !inToRange(first, false)) 2325 throw new NoSuchElementException(); 2326 return first; 2327 } 2328 2329 public K lastKey() { 2330 TrieEntry<K,V> e; 2331 if(toKey == null) { 2332 e = lastEntry(); 2333 } else { 2334 if(toInclusive) 2335 e = floorEntry(toKey); 2336 else 2337 e = lowerEntry(toKey); 2338 } 2339 2340 K last = e != null ? e.getKey() : null; 2341 if (e == null || fromKey != null && !inFromRange(last, false)) 2342 throw new NoSuchElementException(); 2343 return last; 2344 } 2345 2346 private transient Set<Map.Entry<K,V>> entrySet; 2347 2348 public Set<Map.Entry<K,V>> entrySet() { 2349 if(entrySet == null) 2350 entrySet = newSubMapEntrySet(); 2351 return entrySet; 2352 } 2353 2354 protected Set<Map.Entry<K, V>> newSubMapEntrySet() { 2355 return new EntrySetView(); 2356 } 2357 2358 class EntrySetView extends AbstractSet<Map.Entry<K,V>> { 2359 private transient int size = -1, sizeModCount; 2360 2361 public int size() { 2362 if (size == -1 || sizeModCount != PatriciaTrie.this.modCount) { 2363 size = 0; sizeModCount = PatriciaTrie.this.modCount; 2364 Iterator i = iterator(); 2365 while (i.hasNext()) { 2366 size++; 2367 i.next(); 2368 } 2369 } 2370 return size; 2371 } 2372 2373 public boolean isEmpty() { 2374 return !iterator().hasNext(); 2375 } 2376 2377 @SuppressWarnings("unchecked") 2378 public boolean contains(Object o) { 2379 if (!(o instanceof Map.Entry)) 2380 return false; 2381 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 2382 K key = entry.getKey(); 2383 if (!inRange(key)) 2384 return false; 2385 TrieEntry<K, V> node = getEntry(key); 2386 return node != null && 2387 valEquals(node.getValue(), entry.getValue()); 2388 } 2389 2390 @SuppressWarnings("unchecked") 2391 public boolean remove(Object o) { 2392 if (!(o instanceof Map.Entry)) 2393 return false; 2394 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 2395 K key = entry.getKey(); 2396 if (!inRange(key)) 2397 return false; 2398 TrieEntry<K,V> node = getEntry(key); 2399 if (node!=null && valEquals(node.getValue(),entry.getValue())){ 2400 removeEntry(node); 2401 return true; 2402 } 2403 return false; 2404 } 2405 2406 public Iterator<Map.Entry<K,V>> iterator() { 2407 return new SubMapEntryIterator( 2408 (fromKey == null ? firstEntry() : ceilingEntry(fromKey)), 2409 (toKey == null ? null : ceilingEntry(toKey))); 2410 } 2411 } 2412 2413 public SortedMap<K,V> subMap(K fromKey, K toKey) { 2414 if (!inRange2(fromKey)) 2415 throw new IllegalArgumentException("fromKey out of range"); 2416 if (!inRange2(toKey)) 2417 throw new IllegalArgumentException("toKey out of range"); 2418 return new SubMap(fromKey, toKey); 2419 } 2420 2421 public SortedMap<K,V> headMap(K toKey) { 2422 if (!inRange2(toKey)) 2423 throw new IllegalArgumentException("toKey out of range"); 2424 return new SubMap(fromKey, toKey); 2425 } 2426 2427 public SortedMap<K,V> tailMap(K fromKey) { 2428 if (!inRange2(fromKey)) 2429 throw new IllegalArgumentException("fromKey out of range"); 2430 return new SubMap(fromKey, toKey); 2431 } 2432 2433 protected boolean inRange(K key) { 2434 return (fromKey == null || inFromRange(key, false)) && 2435 (toKey == null || inToRange(key, false)); 2436 } 2437 2438 // This form allows the high endpoint (as well as all legit keys) 2439 protected boolean inRange2(K key) { 2440 return (fromKey == null || inFromRange(key, false)) && 2441 (toKey == null || inToRange(key, true)); 2442 } 2443 2444 protected boolean inToRange(K key, boolean forceInclusive) { 2445 int ret = keyAnalyzer.compare(key, toKey); 2446 if(toInclusive || forceInclusive) 2447 return ret <= 0; 2448 else 2449 return ret < 0; 2450 } 2451 2452 protected boolean inFromRange(K key, boolean forceInclusive) { 2453 int ret = keyAnalyzer.compare(key, fromKey); 2454 if (fromInclusive || forceInclusive) 2455 return ret >= 0; 2456 else 2457 return ret > 0; 2458 } 2459 } 2460 2461 private static class EmptyIterator implements Iterator { 2462 public boolean hasNext() { 2463 return false; 2464 } 2465 2466 public Object next() { 2467 throw new NoSuchElementException(); 2468 } 2469 2470 public void remove() { 2471 throw new IllegalStateException(); 2472 } 2473 2474 } 2475}