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