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