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