Find Usages Diff Raw Download HTML Widget Stack Overflow Q&A
Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
1. How to sort a Map on the values in Java?
I am relatively new to Java, and often find that I need to sort a Map on the values. Since the values are not unique, I find myself converting the keySet into an array, and sorting that array through array sort with a custom comparator that sorts on the value associated with the key. Is there an easier way?
2. Big-O summary for Java Collections Framework implementations?
I may be teaching a "Java crash-course" soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the order of the various operations on various collection implementations is. I could take time to generate a summary matrix myself, but if it's already out there in the public domain somewhere, I'd sur...
3. Which data structure would you use: TreeMap or HashMap? (Java)
Description | A Java program to read a text file and print each of the unique words in alphabetical order together with the number of times the word occurs in the text. The program should declare a variable of type Map<String, Integer> to store the words and corresponding frequency of occurrence. Which concrete type, though? TreeMap<String, Number> or HashMap<String, Number>...
4. Hash tables in MATLAB
Does MATLAB have any support for hash tables? Some background I am working on a problem in Matlab that requires a scale-space representation of an image. To do this I create a 2-D Gaussian filter with variance sigma*s^k for k in some range., and then I use each one in turn to filter the image. Now, I want some sort of mapping from k to the filtered image. If k were always an integer, I'd ...
5. How to sort Map values by key in Java
I have a Map in java that has strings for both . Data is like following <"question1", "1">, <"question9", "1">, <"question2", "4">, <"question5", "2"> I want to sort the map based on its Key's. So In the end I will have question1, question2, question3....an so on. Eventually I am trying to get two strings out of this Map. First String: Questions ( in order 1 ..10) and Second S...
6. Accessing the last entry in a Map
How to move a particular HashMap entry to Last position? For Example, I have HashMap values like this: HashMap<String,Integer> map = new HashMap<String,Integer>(); map= {Not-Specified 1, test 2, testtest 3}; "Not-Specified" may come in any position. it may come first or in the middle of the map. But i want to move the "Not-Specified" to the last position. How can I do that? th...
7. Ordered List Map implementation in Java
I was wandering if there is a class out there that implements both Map and List interfaces in Java. I have a data structure that is primarily a Map. I map strings (IDs) to Images. But in a specific part of my code i need to present the user with all the available IDed Images. The only way to do that so far is to write this : for (String id : myMap.keySet()) { // get the image like this "...
8. Better solution than else if with ranged data
I have a simple java method that returns colors based on the HSB value converted from an RGB. It works (needs some tweaking), but I use a series of else if and nested if statements to return the data I want. I had heard that HashMaps and String Factories were better, but I couldn't see how these worked with ranged data. Is there a better solution that works with ranged data like this? Snippet:...
9. How to compare large text files?
I have a general question on your opinion about my "technique". There are 2 textfiles (file_1 and file_2) that need to be compared to each other. Both are very huge (3-4 gigabytes, from 30,000,000 to 45,000,000 lines each). My idea is to read several lines (as many as possible) of file_1 to the memory, then compare those to all lines of file_2. If there's a match, the lines from both files th...
10. Sorting matched arrays in Java
Let's say that I have two arrays (in Java), int[] numbers; and int[] colors; Each ith element of numbers corresponds to its ith element in colors. Ex, numbers = {4,2,1} colors = {0x11, 0x24, 0x01}; Means that number 4 is color 0x11, number 2 is 0x24, etc. I want to sort the numbers array, but then still have it so each element matches up with its pair in colors. Ex. numbers = {1,2,4}; ...
11. Difference between HashMap, LinkedHashMap and SortedMap in java
Map m1 = new HashMap(); m1.put("map", "HashMap"); m1.put("schildt", "java2"); m1.put("mathew", "Hyden"); m1.put("schildt", "java2s"); print(m1.keySet()); print(m1.values()); SortedMap sm = new TreeMap(); sm.put("map", "TreeMap"); sm.put("schildt", "java2"); sm.put("mathew", "Hyden"); sm.put("schildt", "java2s"); print(sm.keySet()); pri...
12. Arrays of Arrays in Java
This is a nasty one for me... I'm a PHP guy working in Java on a JSP project. I know how to do what I'm attempting through too much code and a complete lack of finesse. I'd prefer to do it RIGHT. :) Here is the situation: I'm writing a small display to show customers what days they can water their lawns based on their watering group (ABCDE) and what time of year it is. Our seasons look li...
13. How to sort hash map
how we will be able to sort a hashmap i want so sort in the basis of a value in array list... thanx in advance..............
14. The best way to iterate SortedSet / SortedMap in Java backwards
I need to iterate through SortedMap's entry set (which is a SortedSet) backwards. The code I'm writing is extremely performance-sensitive, as it's going to be called from many places thousands times per second, maybe more. Any advice on doing it the fastest way?
15. Mapping from String to integer - performance of various approaches
Let's say that I need to make a mapping from String to an integer. The integers are unique and form a continuous range starting from 0. That is: Hello -> 0 World -> 1 Foo -> 2 Bar -> 3 Spam -> 4 Eggs -> 5 etc. There are at least two straightforward ways to do it. With a hashmap: HashMap<String, Integer> map = ... int integer = map.get(string); // Plus maybe nul...
16. How to check for key in a Map irrespective of the case?
I want to know whether a particular key is present in a HashMap, so i am using containsKey(key) method. But it is case sensitive ie it does not returns true if there is a key with Name and i am searching for name. So is there any way i can know without bothering the case of the key? thanks
17. Is there a Java data structure that is effectively an ArrayList with double indicies and built-in interpolation?
I am looking for a pre-built Java data structure with the following characteristics: It should look something like an ArrayList but should allow indexing via double-precision rather than integers. Note that this means that it's likely that you'll see indicies that don't line up with the original data points (i.e., asking for the value that corresponds to key "1.5"). EDIT: For clarity, based...
18. Java: libraries for immutable functional-style data structures
This is very similar to another question (Functional Data Structures in Java) but the answers there are not particularly useful. I need to use immutable versions of the standard Java collections (e.g. HashMap / TreeMap / ArrayList / LinkedList / HashSet / TreeSet). By "immutable" I mean immutable in the functional sense (e.g. purely functional data structures), where updating operations on the...
19. Efficiently iterate through all MATCHING keys in a hashmap?
I have a HashMap with millions of entries. Need to retrieve all entries whose keys match a specific set of criteria (in this case, each key is an object with two integer properties; I need to retrieve all keys where each of these integers fall within a specified range). What is the fastest, most efficient way to iterate through all such keys? UPDATE: In this particular case, though I didn't ...
20. Java Class that implements Map and keeps insertion order?
I'm looking for a class in java that has key-value association, but without using hashes. Here is what I'm currently doing: Add values to a Hashtable Get an iterator for the Hashtable.entrySet(). Iterate through all values and: Get a Map.Entry for the iterator Create an object of type Module (a custom class) based on the value. Add the class to a JPanel; Show the panel. The problem with ...
21. What is the difference Hashmap and Treemap?
I started learning Java. When do use Hashmap over Treemap? 
1
   /*
2
    * Copyright 1997-2008 Sun Microsystems, Inc.  All Rights Reserved.
3
    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4
    *
5
    * This code is free software; you can redistribute it and/or modify it
6
    * under the terms of the GNU General Public License version 2 only, as
7
    * published by the Free Software Foundation.  Sun designates this
8
    * particular file as subject to the "Classpath" exception as provided
9
    * by Sun in the LICENSE file that accompanied this code.
10
   *
11
   * This code is distributed in the hope that it will be useful, but WITHOUT
12
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
   * version 2 for more details (a copy is included in the LICENSE file that
15
   * accompanied this code).
16
   *
17
   * You should have received a copy of the GNU General Public License version
18
   * 2 along with this work; if not, write to the Free Software Foundation,
19
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20
   *
21
   * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22
   * CA 95054 USA or visit www.sun.com if you need additional information or
23
   * have any questions.
24
   */
25
  
26
  package java.util;

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map: 

   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

The iterators returned by the iterator method of the collections returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put.)

This class is a member of the Java Collections Framework.

Parameters:
<K> the type of keys maintained by this map
<V> the type of mapped values
Author(s):
Josh Bloch and Doug Lea
Since:
1.2
See also:
Map
HashMap
Hashtable
java.lang.Comparable
Comparator
Collection
103
 
104
 
105
 public class TreeMap<K,V>
106
     extends AbstractMap<K,V>
107
     implements NavigableMap<K,V>, Cloneable, java.io.Serializable
108
 {
    
The comparator used to maintain order in this tree map, or null if it uses the natural ordering of its keys.

Serial:
114
 
115
     private final Comparator<? super K> comparator;
116
 
117
     private transient Entry<K,V> root = null;

    
The number of entries in the tree 
121
 
122
     private transient int size = 0;

    
The number of structural modifications to the tree. 
126
 
127
     private transient int modCount = 0;

    
Constructs a new, empty tree map, using the natural ordering of its keys. All keys inserted into the map must implement the java.lang.Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any keys k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint (for example, the user attempts to put a string key into a map whose keys are integers), the put(Object key, Object value) call will throw a ClassCastException. 
140
 
141
     public TreeMap() {
142
          = null;
143
     }

    
Constructs a new, empty tree map, ordered according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator: comparator.compare(k1, k2) must not throw a ClassCastException for any keys k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint, the put(Object key, Object value) call will throw a ClassCastException.

Parameters:
comparator the comparator that will be used to order this map. If null, the natural ordering of the keys will be used.
158
 
159
     public TreeMap(Comparator<? super K> comparator) {
160
         this. = comparator;
161
     }

    
Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys. All keys inserted into the new map must implement the java.lang.Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any keys k1 and k2 in the map. This method runs in n*log(n) time.

Parameters:
m the map whose mappings are to be placed in this map
Throws:
java.lang.ClassCastException if the keys in m are not java.lang.Comparable, or are not mutually comparable
java.lang.NullPointerException if the specified map is null
176
 
177
     public TreeMap(Map<? extends K, ? extends V> m) {
178
          = null;
179
         putAll(m);
180
     }

    
Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map. This method runs in linear time.

Parameters:
m the sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map
Throws:
java.lang.NullPointerException if the specified map is null
190
 
191
     public TreeMap(SortedMap<K, ? extends V> m) {
192
          = m.comparator();
193
         try {
194
             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
195
         } catch (java.io.IOException cannotHappen) {
196
         } catch (ClassNotFoundException cannotHappen) {
197
         }
198
     }
199
 
200
 
201
     // Query Operations
202
 
    
Returns the number of key-value mappings in this map.

Returns:
the number of key-value mappings in this map
207
 
208
     public int size() {
209
         return ;
210
     }

    
Returns true if this map contains a mapping for the specified key.

Parameters:
key key whose presence in this map is to be tested
Returns:
true if this map contains a mapping for the specified key
Throws:
java.lang.ClassCastException if the specified key cannot be compared with the keys currently in the map
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
224
 
225
     public boolean containsKey(Object key) {
226
         return getEntry(key) != null;
227
     }

    
Returns true if this map maps one or more keys to the specified value. More formally, returns true if and only if this map contains at least one mapping to a value v such that (value==null ? v==null : value.equals(v)). This operation will probably require time linear in the map size for most implementations.

Parameters:
value value whose presence in this map is to be tested
Returns:
true if a mapping to value exists; false otherwise
Since:
1.2
241
 
242
     public boolean containsValue(Object value) {
243
         for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
244
             if (valEquals(value, e.value))
245
                 return true;
246
         return false;
247
     }

    
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key k to a value v such that key compares equal to k according to the map's ordering, then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

A return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey operation may be used to distinguish these two cases.

Throws:
java.lang.ClassCastException if the specified key cannot be compared with the keys currently in the map
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
270
 
271
     public V get(Object key) {
272
         Entry<K,V> p = getEntry(key);
273
         return (p==null ? null : p.value);
274
     }
275
 
276
     public Comparator<? super K> comparator() {
277
         return ;
278
     }

    

Throws:
NoSuchElementException
282
 
283
     public K firstKey() {
284
         return key(getFirstEntry());
285
     }

    

Throws:
NoSuchElementException
289
 
290
     public K lastKey() {
291
         return key(getLastEntry());
292
     }

    
Copies all of the mappings from the specified map to this map. These mappings replace any mappings that this map had for any of the keys currently in the specified map.

Parameters:
map mappings to be stored in this map
Throws:
java.lang.ClassCastException if the class of a key or value in the specified map prevents it from being stored in this map
java.lang.NullPointerException if the specified map is null or the specified map contains a null key and this map does not permit null keys
305
 
306
     public void putAll(Map<? extends K, ? extends V> map) {
307
         int mapSize = map.size();
308
         if (==0 && mapSize!=0 && map instanceof SortedMap) {
309
             Comparator c = ((SortedMap)map).comparator();
310
             if (c ==  || (c != null && c.equals())) {
311
                 ++;
312
                 try {
313
                     buildFromSorted(mapSize, map.entrySet().iterator(),
314
                                     null, null);
315
                 } catch (java.io.IOException cannotHappen) {
316
                 } catch (ClassNotFoundException cannotHappen) {
317
                 }
318
                 return;
319
             }
320
         }
321
         super.putAll(map);
322
     }

    
Returns this map's entry for the given key, or null if the map does not contain an entry for the key.

Returns:
this map's entry for the given key, or null if the map does not contain an entry for the key
Throws:
java.lang.ClassCastException if the specified key cannot be compared with the keys currently in the map
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
335
 
336
     final Entry<K,V> getEntry(Object key) {
337
         // Offload comparator-based version for sake of performance
338
         if ( != null)
339
             return getEntryUsingComparator(key);
340
         if (key == null)
341
             throw new NullPointerException();
342
         Comparable<? super K> k = (Comparable<? super K>) key;
343
         Entry<K,V> p = ;
344
         while (p != null) {
345
             int cmp = k.compareTo(p.key);
346
             if (cmp < 0)
347
                 p = p.left;
348
             else if (cmp > 0)
349
                 p = p.right;
350
             else
351
                 return p;
352
         }
353
         return null;
354
     }

    
Version of getEntry using comparator. Split off from getEntry for performance. (This is not worth doing for most methods, that are less dependent on comparator performance, but is worthwhile here.) 
361
 
362
     final Entry<K,V> getEntryUsingComparator(Object key) {
363
         K k = (K) key;
364
         Comparator<? super K> cpr = ;
365
         if (cpr != null) {
366
             Entry<K,V> p = ;
367
             while (p != null) {
368
                 int cmp = cpr.compare(k, p.key);
369
                 if (cmp < 0)
370
                     p = p.left;
371
                 else if (cmp > 0)
372
                     p = p.right;
373
                 else
374
                     return p;
375
             }
376
         }
377
         return null;
378
     }

    
Gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the least key greater than the specified key; if no such entry exists (i.e., the greatest key in the Tree is less than the specified key), returns null. 
385
 
386
     final Entry<K,V> getCeilingEntry(K key) {
387
         Entry<K,V> p = ;
388
         while (p != null) {
389
             int cmp = compare(key, p.key);
390
             if (cmp < 0) {
391
                 if (p.left != null)
392
                     p = p.left;
393
                 else
394
                     return p;
395
             } else if (cmp > 0) {
396
                 if (p.right != null) {
397
                     p = p.right;
398
                 } else {
399
                     Entry<K,V> parent = p.parent;
400
                     Entry<K,V> ch = p;
401
                     while (parent != null && ch == parent.right) {
402
                         ch = parent;
403
                         parent = parent.parent;
404
                     }
405
                     return parent;
406
                 }
407
             } else
408
                 return p;
409
         }
410
         return null;
411
     }

    
Gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the greatest key less than the specified key; if no such entry exists, returns null. 
417
 
418
     final Entry<K,V> getFloorEntry(K key) {
419
         Entry<K,V> p = ;
420
         while (p != null) {
421
             int cmp = compare(key, p.key);
422
             if (cmp > 0) {
423
                 if (p.right != null)
424
                     p = p.right;
425
                 else
426
                     return p;
427
             } else if (cmp < 0) {
428
                 if (p.left != null) {
429
                     p = p.left;
430
                 } else {
431
                     Entry<K,V> parent = p.parent;
432
                     Entry<K,V> ch = p;
433
                     while (parent != null && ch == parent.left) {
434
                         ch = parent;
435
                         parent = parent.parent;
436
                     }
437
                     return parent;
438
                 }
439
             } else
440
                 return p;
441
 
442
         }
443
         return null;
444
     }

    
Gets the entry for the least key greater than the specified key; if no such entry exists, returns the entry for the least key greater than the specified key; if no such entry exists returns null. 
451
 
452
     final Entry<K,V> getHigherEntry(K key) {
453
         Entry<K,V> p = ;
454
         while (p != null) {
455
             int cmp = compare(key, p.key);
456
             if (cmp < 0) {
457
                 if (p.left != null)
458
                     p = p.left;
459
                 else
460
                     return p;
461
             } else {
462
                 if (p.right != null) {
463
                     p = p.right;
464
                 } else {
465
                     Entry<K,V> parent = p.parent;
466
                     Entry<K,V> ch = p;
467
                     while (parent != null && ch == parent.right) {
468
                         ch = parent;
469
                         parent = parent.parent;
470
                     }
471
                     return parent;
472
                 }
473
             }
474
         }
475
         return null;
476
     }

    
Returns the entry for the greatest key less than the specified key; if no such entry exists (i.e., the least key in the Tree is greater than the specified key), returns null. 
482
 
483
     final Entry<K,V> getLowerEntry(K key) {
484
         Entry<K,V> p = ;
485
         while (p != null) {
486
             int cmp = compare(key, p.key);
487
             if (cmp > 0) {
488
                 if (p.right != null)
489
                     p = p.right;
490
                 else
491
                     return p;
492
             } else {
493
                 if (p.left != null) {
494
                     p = p.left;
495
                 } else {
496
                     Entry<K,V> parent = p.parent;
497
                     Entry<K,V> ch = p;
498
                     while (parent != null && ch == parent.left) {
499
                         ch = parent;
500
                         parent = parent.parent;
501
                     }
502
                     return parent;
503
                 }
504
             }
505
         }
506
         return null;
507
     }

    
Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

Parameters:
key key with which the specified value is to be associated
value value to be associated with the specified key
Returns:
the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
Throws:
java.lang.ClassCastException if the specified key cannot be compared with the keys currently in the map
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
526
 
527
     public V put(K key, V value) {
528
         Entry<K,V> t = ;
529
         if (t == null) {
530
             // TBD:
531
             // 5045147: (coll) Adding null to an empty TreeSet should
532
             // throw NullPointerException
533
             //
534
             // compare(key, key); // type check
535
              = new Entry<K,V>(key, value, null);
536
              = 1;
537
             ++;
538
             return null;
539
         }
540
         int cmp;
541
         Entry<K,V> parent;
542
         // split comparator and comparable paths
543
         Comparator<? super K> cpr = ;
544
         if (cpr != null) {
545
             do {
546
                 parent = t;
547
                 cmp = cpr.compare(key, t.key);
548
                 if (cmp < 0)
549
                     t = t.left;
550
                 else if (cmp > 0)
551
                     t = t.right;
552
                 else
553
                     return t.setValue(value);
554
             } while (t != null);
555
         }
556
         else {
557
             if (key == null)
558
                 throw new NullPointerException();
559
             Comparable<? super K> k = (Comparable<? super K>) key;
560
             do {
561
                 parent = t;
562
                 cmp = k.compareTo(t.key);
563
                 if (cmp < 0)
564
                     t = t.left;
565
                 else if (cmp > 0)
566
                     t = t.right;
567
                 else
568
                     return t.setValue(value);
569
             } while (t != null);
570
         }
571
         Entry<K,V> e = new Entry<K,V>(key, value, parent);
572
         if (cmp < 0)
573
             parent.left = e;
574
         else
575
             parent.right = e;
576
         fixAfterInsertion(e);
577
         ++;
578
         ++;
579
         return null;
580
     }

    
Removes the mapping for this key from this TreeMap if present.

Parameters:
key key for which mapping should be removed
Returns:
the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
Throws:
java.lang.ClassCastException if the specified key cannot be compared with the keys currently in the map
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
595
 
596
     public V remove(Object key) {
597
         Entry<K,V> p = getEntry(key);
598
         if (p == null)
599
             return null;
600
 
601
         V oldValue = p.value;
602
         deleteEntry(p);
603
         return oldValue;
604
     }

    
Removes all of the mappings from this map. The map will be empty after this call returns. 
609
 
610
     public void clear() {
611
         ++;
612
          = 0;
613
          = null;
614
     }

    
Returns a shallow copy of this TreeMap instance. (The keys and values themselves are not cloned.)

Returns:
a shallow copy of this map
621
 
622
     public Object clone() {
623
         TreeMap<K,V> clone = null;
624
         try {
625
             clone = (TreeMap<K,V>) super.clone();
626
         } catch (CloneNotSupportedException e) {
627
             throw new InternalError();
628
         }
629
 
630
         // Put clone into "virgin" state (except for comparator)
631
         clone.root = null;
632
         clone.size = 0;
633
         clone.modCount = 0;
634
         clone.entrySet = null;
635
         clone.navigableKeySet = null;
636
         clone.descendingMap = null;
637
 
638
         // Initialize clone with our mappings
639
         try {
640
             clone.buildFromSorted(, entrySet().iterator(), null, null);
641
         } catch (java.io.IOException cannotHappen) {
642
         } catch (ClassNotFoundException cannotHappen) {
643
         }
644
 
645
         return clone;
646
     }
647
 
648
     // NavigableMap API methods
649
 
    

Since:
1.6
652
 
653
     public Map.Entry<K,V> firstEntry() {
654
         return exportEntry(getFirstEntry());
655
     }

    

Since:
1.6
659
 
660
     public Map.Entry<K,V> lastEntry() {
661
         return exportEntry(getLastEntry());
662
     }

    

Since:
1.6
666
 
667
     public Map.Entry<K,V> pollFirstEntry() {
668
         Entry<K,V> p = getFirstEntry();
669
         Map.Entry<K,V> result = exportEntry(p);
670
         if (p != null)
671
             deleteEntry(p);
672
         return result;
673
     }

    

Since:
1.6
677
 
678
     public Map.Entry<K,V> pollLastEntry() {
679
         Entry<K,V> p = getLastEntry();
680
         Map.Entry<K,V> result = exportEntry(p);
681
         if (p != null)
682
             deleteEntry(p);
683
         return result;
684
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
692
 
693
     public Map.Entry<K,V> lowerEntry(K key) {
694
         return exportEntry(getLowerEntry(key));
695
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
703
 
704
     public K lowerKey(K key) {
705
         return keyOrNull(getLowerEntry(key));
706
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
714
 
715
     public Map.Entry<K,V> floorEntry(K key) {
716
         return exportEntry(getFloorEntry(key));
717
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
725
 
726
     public K floorKey(K key) {
727
         return keyOrNull(getFloorEntry(key));
728
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
736
 
737
     public Map.Entry<K,V> ceilingEntry(K key) {
738
         return exportEntry(getCeilingEntry(key));
739
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
747
 
748
     public K ceilingKey(K key) {
749
         return keyOrNull(getCeilingEntry(key));
750
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
758
 
759
     public Map.Entry<K,V> higherEntry(K key) {
760
         return exportEntry(getHigherEntry(key));
761
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys
Since:
1.6
769
 
770
     public K higherKey(K key) {
771
         return keyOrNull(getHigherEntry(key));
772
     }
773
 
774
     // Views
775
 
    
Fields initialized to contain an instance of the entry set view the first time this view is requested. Views are stateless, so there's no reason to create more than one. 
780
 
781
     private transient EntrySet entrySet = null;
782
     private transient KeySet<K> navigableKeySet = null;
783
     private transient NavigableMap<K,V> descendingMap = null;

    
Returns a Set view of the keys contained in this map. The set's iterator returns the keys in ascending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. 
798
 
799
     public Set<K> keySet() {
800
         return navigableKeySet();
801
     }

    

Since:
1.6
805
 
806
     public NavigableSet<K> navigableKeySet() {
807
         KeySet<K> nks = ;
808
         return (nks != null) ? nks : ( = new KeySet(this));
809
     }

    

Since:
1.6
813
 
814
     public NavigableSet<K> descendingKeySet() {
815
         return descendingMap().navigableKeySet();
816
     }

    
Returns a Collection view of the values contained in this map. The collection's iterator returns the values in ascending order of the corresponding keys. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. If the map is modified while an iteration over the collection is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations. 
832
 
833
     public Collection<V> values() {
834
         Collection<V> vs = ;
835
         return (vs != null) ? vs : ( = new Values());
836
     }

    
Returns a Set view of the mappings contained in this map. The set's iterator returns the entries in ascending key order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator) the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations. 
852
 
853
     public Set<Map.Entry<K,V>> entrySet() {
854
         EntrySet es = ;
855
         return (es != null) ? es : ( = new EntrySet());
856
     }

    

Since:
1.6
860
 
861
     public NavigableMap<K, V> descendingMap() {
862
         NavigableMap<K, V> km = ;
863
         return (km != null) ? km :
864
             ( = new DescendingSubMap(this,
865
                                                   true, null, true,
866
                                                   true, null, true));
867
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if fromKey or toKey is null and this map uses natural ordering, or its comparator does not permit null keys
java.lang.IllegalArgumentException
Since:
1.6
876
 
877
     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
878
                                     K toKey,   boolean toInclusive) {
879
         return new AscendingSubMap(this,
880
                                    false, fromKey, fromInclusive,
881
                                    false, toKey,   toInclusive);
882
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if toKey is null and this map uses natural ordering, or its comparator does not permit null keys
java.lang.IllegalArgumentException
Since:
1.6
891
 
892
     public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
893
         return new AscendingSubMap(this,
894
                                    true,  null,  true,
895
                                    false, toKey, inclusive);
896
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if fromKey is null and this map uses natural ordering, or its comparator does not permit null keys
java.lang.IllegalArgumentException
Since:
1.6
905
 
906
     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
907
         return new AscendingSubMap(this,
908
                                    false, fromKey, inclusive,
909
                                    true,  null,    true);
910
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if fromKey or toKey is null and this map uses natural ordering, or its comparator does not permit null keys
java.lang.IllegalArgumentException
918
 
919
     public SortedMap<K,V> subMap(K fromKey, K toKey) {
920
         return subMap(fromKey, true, toKey, false);
921
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if toKey is null and this map uses natural ordering, or its comparator does not permit null keys
java.lang.IllegalArgumentException
929
 
930
     public SortedMap<K,V> headMap(K toKey) {
931
         return headMap(toKey, false);
932
     }

    

Throws:
java.lang.ClassCastException
java.lang.NullPointerException if fromKey is null and this map uses natural ordering, or its comparator does not permit null keys
java.lang.IllegalArgumentException
940
 
941
     public SortedMap<K,V> tailMap(K fromKey) {
942
         return tailMap(fromKey, true);
943
     }
944
 
945
     // View class support
946
 
947
     class Values extends AbstractCollection<V> {
948
         public Iterator<V> iterator() {
949
             return new ValueIterator(getFirstEntry());
950
         }
951
 
952
         public int size() {
953
             return TreeMap.this.size();
954
         }
955
 
956
         public boolean contains(Object o) {
957
             return TreeMap.this.containsValue(o);
958
         }
959
 
960
         public boolean remove(Object o) {
961
             for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
962
                 if (valEquals(e.getValue(), o)) {
963
                     deleteEntry(e);
964
                     return true;
965
                 }
966
             }
967
             return false;
968
         }
969
 
970
         public void clear() {
971
             TreeMap.this.clear();
972
         }
973
     }
974
 
975
     class EntrySet extends AbstractSet<Map.Entry<K,V>> {
976
         public Iterator<Map.Entry<K,V>> iterator() {
977
             return new EntryIterator(getFirstEntry());
978
         }
979
 
980
         public boolean contains(Object o) {
981
             if (!(o instanceof Map.Entry))
982
                 return false;
983
             Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
984
             V value = entry.getValue();
985
             Entry<K,V> p = getEntry(entry.getKey());
986
             return p != null && valEquals(p.getValue(), value);
987
         }
988
 
989
         public boolean remove(Object o) {
990
             if (!(o instanceof Map.Entry))
991
                 return false;
992
             Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
993
             V value = entry.getValue();
994
             Entry<K,V> p = getEntry(entry.getKey());
995
             if (p != null && valEquals(p.getValue(), value)) {
996
                 deleteEntry(p);
997
                 return true;
998
             }
999
             return false;
1000
        }
1002
        public int size() {
1003
            return TreeMap.this.size();
1004
        }
1006
        public void clear() {
1007
            TreeMap.this.clear();
1008
        }
1009
    }
1011
    /*
1012
     * Unlike Values and EntrySet, the KeySet class is static,
1013
     * delegating to a NavigableMap to allow use by SubMaps, which
1014
     * outweighs the ugliness of needing type-tests for the following
1015
     * Iterator methods that are defined appropriately in main versus
1016
     * submap classes.
1017
     */
1019
    Iterator<K> keyIterator() {
1020
        return new KeyIterator(getFirstEntry());
1021
    }
1024
        return new DescendingKeyIterator(getLastEntry());
1025
    }
1027
    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1028
        private final NavigableMap<E, Object> m;
1029
        KeySet(NavigableMap<E,Object> map) {  = map; }
1031
        public Iterator<E> iterator() {
1032
            if ( instanceof TreeMap)
1033
                return ((TreeMap<E,Object>)).keyIterator();
1034
            else
1035
                return (Iterator<E>)(((TreeMap.NavigableSubMap)).keyIterator());
1036
        }
1038
        public Iterator<E> descendingIterator() {
1039
            if ( instanceof TreeMap)
1040
                return ((TreeMap<E,Object>)).descendingKeyIterator();
1041
            else
1042
                return (Iterator<E>)(((TreeMap.NavigableSubMap)).descendingKeyIterator());
1043
        }
1045
        public int size() { return .size(); }
1046
        public boolean isEmpty() { return .isEmpty(); }
1047
        public boolean contains(Object o) { return .containsKey(o); }
1048
        public void clear() { .clear(); }
1049
        public E lower(E e) { return .lowerKey(e); }
1050
        public E floor(E e) { return .floorKey(e); }
1051
        public E ceiling(E e) { return .ceilingKey(e); }
1052
        public E higher(E e) { return .higherKey(e); }
1053
        public E first() { return .firstKey(); }
1054
        public E last() { return .lastKey(); }
1055
        public Comparator<? super E> comparator() { return .comparator(); }
1056
        public E pollFirst() {
1057
            Map.Entry<E,Object> e = .pollFirstEntry();
1058
            return e == null? null : e.getKey();
1059
        }
1060
        public E pollLast() {
1061
            Map.Entry<E,Object> e = .pollLastEntry();
1062
            return e == null? null : e.getKey();
1063
        }
1064
        public boolean remove(Object o) {
1065
            int oldSize = size();
1066
            .remove(o);
1067
            return size() != oldSize;
1068
        }
1069
        public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1070
                                      E toElement,   boolean toInclusive) {
1071
            return new TreeSet<E>(.subMap(fromElement, fromInclusive,
1072
                                           toElement,   toInclusive));
1073
        }
1074
        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1075
            return new TreeSet<E>(.headMap(toElement, inclusive));
1076
        }
1077
        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1078
            return new TreeSet<E>(.tailMap(fromElement, inclusive));
1079
        }
1080
        public SortedSet<E> subSet(E fromElement, E toElement) {
1081
            return subSet(fromElement, true, toElement, false);
1082
        }
1083
        public SortedSet<E> headSet(E toElement) {
1084
            return headSet(toElement, false);
1085
        }
1086
        public SortedSet<E> tailSet(E fromElement) {
1087
            return tailSet(fromElement, true);
1088
        }
1089
        public NavigableSet<E> descendingSet() {
1090
            return new TreeSet(.descendingMap());
1091
        }
1092
    }

    
Base class for TreeMap Iterators 
1097
    abstract class PrivateEntryIterator<T> implements Iterator<T> {
1098
        Entry<K,V> next;
1099
        Entry<K,V> lastReturned;
1100
        int expectedModCount;
1102
        PrivateEntryIterator(Entry<K,V> first) {
1103
             = ;
1104
             = null;
1105
             = first;
1106
        }
1108
        public final boolean hasNext() {
1109
            return  != null;
1110
        }
1112
        final Entry<K,V> nextEntry() {
1113
            Entry<K,V> e = ;
1114
            if (e == null)
1115
                throw new NoSuchElementException();
1116
            if ( != )
1117
                throw new ConcurrentModificationException();
1118
             = successor(e);
1119
             = e;
1120
            return e;
1121
        }
1123
        final Entry<K,V> prevEntry() {
1124
            Entry<K,V> e = ;
1125
            if (e == null)
1126
                throw new NoSuchElementException();
1127
            if ( != )
1128
                throw new ConcurrentModificationException();
1129
             = predecessor(e);
1130
             = e;
1131
            return e;
1132
        }
1134
        public void remove() {
1135
            if ( == null)
1136
                throw new IllegalStateException();
1137
            if ( != )
1138
                throw new ConcurrentModificationException();
1139
            // deleted entries are replaced by their successors
1140
            if (. != null && . != null)
1141
                 = ;
1142
            deleteEntry();
1143
             = ;
1144
             = null;
1145
        }
1146
    }
1148
    final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1149
        EntryIterator(Entry<K,V> first) {
1150
            super(first);
1151
        }
1152
        public Map.Entry<K,V> next() {
1153
            return nextEntry();
1154
        }
1155
    }
1157
    final class ValueIterator extends PrivateEntryIterator<V> {
1158
        ValueIterator(Entry<K,V> first) {
1159
            super(first);
1160
        }
1161
        public V next() {
1162
            return nextEntry().;
1163
        }
1164
    }
1166
    final class KeyIterator extends PrivateEntryIterator<K> {
1167
        KeyIterator(Entry<K,V> first) {
1168
            super(first);
1169
        }
1170
        public K next() {
1171
            return nextEntry().;
1172
        }
1173
    }
1175
    final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1176
        DescendingKeyIterator(Entry<K,V> first) {
1177
            super(first);
1178
        }
1179
        public K next() {
1180
            return prevEntry().;
1181
        }
1182
    }
1184
    // Little utilities
1185

    
Compares two keys using the correct comparison method for this TreeMap. 
1189
    final int compare(Object k1, Object k2) {
1190
        return ==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1191
            : .compare((K)k1, (K)k2);
1192
    }

    
Test two values for equality. Differs from o1.equals(o2) only in that it copes with null o1 properly. 
1198
    final static boolean valEquals(Object o1, Object o2) {
1199
        return (o1==null ? o2==null : o1.equals(o2));
1200
    }

    
Return SimpleImmutableEntry for entry, or null if null 
1205
    static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1206
        return e == null? null :
1207
            new AbstractMap.SimpleImmutableEntry<K,V>(e);
1208
    }

    
Return key for entry, or null if null 
1213
    static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1214
        return e == null? null : e.key;
1215
    }

    
Returns the key corresponding to the specified Entry.

Throws:
NoSuchElementException if the Entry is null
1221
    static <K> K key(Entry<K,?> e) {
1222
        if (e==null)
1223
            throw new NoSuchElementException();
1224
        return e.key;
1225
    }
1228
    // SubMaps
1229

    
Dummy value serving as unmatchable fence key for unbounded SubMapIterators 
1234
    private static final Object UNBOUNDED = new Object();

    

Serial:
include
1239
    static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1240
        implements NavigableMap<K,V>, java.io.Serializable {
        
The backing map. 
1244
        final TreeMap<K,V> m;

        
Endpoints are represented as triples (fromStart, lo, loInclusive) and (toEnd, hi, hiInclusive). If fromStart is true, then the low (absolute) bound is the start of the backing map, and the other values are ignored. Otherwise, if loInclusive is true, lo is the inclusive bound, else lo is the exclusive bound. Similarly for the upper bound. 
1254
        final K lo, hi;
1255
        final boolean fromStart, toEnd;
1256
        final boolean loInclusive, hiInclusive;
1258
        NavigableSubMap(TreeMap<K,V> m,
1259
                        boolean fromStart, K lo, boolean loInclusive,
1260
                        boolean toEnd,     K hi, boolean hiInclusive) {
1261
            if (!fromStart && !toEnd) {
1262
                if (m.compare(lo, hi) > 0)
1263
                    throw new IllegalArgumentException("fromKey > toKey");
1264
            } else {
1265
                if (!fromStart) // type check
1266
                    m.compare(lo, lo);
1267
                if (!toEnd)
1268
                    m.compare(hi, hi);
1269
            }
1271
            this. = m;
1272
            this. = fromStart;
1273
            this. = lo;
1274
            this. = loInclusive;
1275
            this. = toEnd;
1276
            this. = hi;
1277
            this. = hiInclusive;
1278
        }
1280
        // internal utilities
1282
        final boolean tooLow(Object key) {
1283
            if (!) {
1284
                int c = .compare(key, );
1285
                if (c < 0 || (c == 0 && !))
1286
                    return true;
1287
            }
1288
            return false;
1289
        }
1291
        final boolean tooHigh(Object key) {
1292
            if (!) {
1293
                int c = .compare(key, );
1294
                if (c > 0 || (c == 0 && !))
1295
                    return true;
1296
            }
1297
            return false;
1298
        }
1300
        final boolean inRange(Object key) {
1301
            return !tooLow(key) && !tooHigh(key);
1302
        }
1304
        final boolean inClosedRange(Object key) {
1305
            return ( || .compare(key, ) >= 0)
1306
                && ( || .compare(, key) >= 0);
1307
        }
1309
        final boolean inRange(Object key, boolean inclusive) {
1310
            return inclusive ? inRange(key) : inClosedRange(key);
1311
        }
1313
        /*
1314
         * Absolute versions of relation operations.
1315
         * Subclasses map to these using like-named "sub"
1316
         * versions that invert senses for descending maps
1317
         */
1319
        final TreeMap.Entry<K,V> absLowest() {
1320
            TreeMap.Entry<K,V> e =
1321
                ( ?  .getFirstEntry() :
1322
                 ( ? .getCeilingEntry() :
1323
                                .getHigherEntry()));
1324
            return (e == null || tooHigh(e.key)) ? null : e;
1325
        }
1327
        final TreeMap.Entry<K,V> absHighest() {
1328
            TreeMap.Entry<K,V> e =
1329
                ( ?  .getLastEntry() :
1330
                 ( ?  .getFloorEntry() :
1331
                                 .getLowerEntry()));
1332
            return (e == null || tooLow(e.key)) ? null : e;
1333
        }
1335
        final TreeMap.Entry<K,V> absCeiling(K key) {
1336
            if (tooLow(key))
1337
                return absLowest();
1338
            TreeMap.Entry<K,V> e = .getCeilingEntry(key);
1339
            return (e == null || tooHigh(e.key)) ? null : e;
1340
        }
1342
        final TreeMap.Entry<K,V> absHigher(K key) {
1343
            if (tooLow(key))
1344
                return absLowest();
1345
            TreeMap.Entry<K,V> e = .getHigherEntry(key);
1346
            return (e == null || tooHigh(e.key)) ? null : e;
1347
        }
1349
        final TreeMap.Entry<K,V> absFloor(K key) {
1350
            if (tooHigh(key))
1351
                return absHighest();
1352
            TreeMap.Entry<K,V> e = .getFloorEntry(key);
1353
            return (e == null || tooLow(e.key)) ? null : e;
1354
        }
1356
        final TreeMap.Entry<K,V> absLower(K key) {
1357
            if (tooHigh(key))
1358
                return absHighest();
1359
            TreeMap.Entry<K,V> e = .getLowerEntry(key);
1360
            return (e == null || tooLow(e.key)) ? null : e;
1361
        }

        
Returns the absolute high fence for ascending traversal
1364
        final TreeMap.Entry<K,V> absHighFence() {
1365
            return ( ? null : ( ?
1366
                                    .getHigherEntry() :
1367
                                    .getCeilingEntry()));
1368
        }

        
Return the absolute low fence for descending traversal 
1371
        final TreeMap.Entry<K,V> absLowFence() {
1372
            return ( ? null : ( ?
1373
                                        .getLowerEntry() :
1374
                                        .getFloorEntry()));
1375
        }
1377
        // Abstract methods defined in ascending vs descending classes
1378
        // These relay to the appropriate absolute versions
1380
        abstract TreeMap.Entry<K,V> subLowest();
1381
        abstract TreeMap.Entry<K,V> subHighest();
1382
        abstract TreeMap.Entry<K,V> subCeiling(K key);
1383
        abstract TreeMap.Entry<K,V> subHigher(K key);
1384
        abstract TreeMap.Entry<K,V> subFloor(K key);
1385
        abstract TreeMap.Entry<K,V> subLower(K key);

        
Returns ascending iterator from the perspective of this submap
1388
        abstract Iterator<K> keyIterator();

        
Returns descending iterator from the perspective of this submap
1391
        abstract Iterator<K> descendingKeyIterator();
1393
        // public methods
1395
        public boolean isEmpty() {
1396
            return ( && ) ? .isEmpty() : entrySet().isEmpty();
1397
        }
1399
        public int size() {
1400
            return ( && ) ? .size() : entrySet().size();
1401
        }
1403
        public final boolean containsKey(Object key) {
1404
            return inRange(key) && .containsKey(key);
1405
        }
1407
        public final V put(K key, V value) {
1408
            if (!inRange(key))
1409
                throw new IllegalArgumentException("key out of range");
1410
            return .put(key, value);
1411
        }
1413
        public final V get(Object key) {
1414
            return !inRange(key)? null :  .get(key);
1415
        }
1417
        public final V remove(Object key) {
1418
            return !inRange(key)? null  : .remove(key);
1419
        }
1421
        public final Map.Entry<K,V> ceilingEntry(K key) {
1422
            return exportEntry(subCeiling(key));
1423
        }
1425
        public final K ceilingKey(K key) {
1426
            return keyOrNull(subCeiling(key));
1427
        }
1429
        public final Map.Entry<K,V> higherEntry(K key) {
1430
            return exportEntry(subHigher(key));
1431
        }
1433
        public final K higherKey(K key) {
1434
            return keyOrNull(subHigher(key));
1435
        }
1437
        public final Map.Entry<K,V> floorEntry(K key) {
1438
            return exportEntry(subFloor(key));
1439
        }
1441
        public final K floorKey(K key) {
1442
            return keyOrNull(subFloor(key));
1443
        }
1445
        public final Map.Entry<K,V> lowerEntry(K key) {
1446
            return exportEntry(subLower(key));
1447
        }
1449
        public final K lowerKey(K key) {
1450
            return keyOrNull(subLower(key));
1451
        }
1453
        public final K firstKey() {
1454
            return key(subLowest());
1455
        }
1457
        public final K lastKey() {
1458
            return key(subHighest());
1459
        }
1461
        public final Map.Entry<K,V> firstEntry() {
1462
            return exportEntry(subLowest());
1463
        }
1465
        public final Map.Entry<K,V> lastEntry() {
1466
            return exportEntry(subHighest());
1467
        }
1469
        public final Map.Entry<K,V> pollFirstEntry() {
1470
            TreeMap.Entry<K,V> e = subLowest();
1471
            Map.Entry<K,V> result = exportEntry(e);
1472
            if (e != null)
1473
                .deleteEntry(e);
1474
            return result;
1475
        }
1477
        public final Map.Entry<K,V> pollLastEntry() {
1478
            TreeMap.Entry<K,V> e = subHighest();
1479
            Map.Entry<K,V> result = exportEntry(e);
1480
            if (e != null)
1481
                .deleteEntry(e);
1482
            return result;
1483
        }
1485
        // Views
1486
        transient NavigableMap<K,V> descendingMapView = null;
1487
        transient EntrySetView entrySetView = null;
1488
        transient KeySet<K> navigableKeySetView = null;
1490
        public final NavigableSet<K> navigableKeySet() {
1491
            KeySet<K> nksv = ;
1492
            return (nksv != null) ? nksv :
1493
                ( = new TreeMap.KeySet(this));
1494
        }
1496
        public final Set<K> keySet() {
1497
            return navigableKeySet();
1498
        }
1500
        public NavigableSet<K> descendingKeySet() {
1501
            return descendingMap().navigableKeySet();
1502
        }
1504
        public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1505
            return subMap(fromKey, true, toKey, false);
1506
        }
1508
        public final SortedMap<K,V> headMap(K toKey) {
1509
            return headMap(toKey, false);
1510
        }
1512
        public final SortedMap<K,V> tailMap(K fromKey) {
1513
            return tailMap(fromKey, true);
1514
        }
1516
        // View classes
1518
        abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1519
            private transient int size = -1, sizeModCount;
1521
            public int size() {
1522
                if ( && )
1523
                    return .size();
1524
                if ( == -1 ||  != .) {
1525
                     = .;
1526
                     = 0;
1527
                    Iterator i = iterator();
1528
                    while (i.hasNext()) {
1529
                        ++;
1530
                        i.next();
1531
                    }
1532
                }
1533
                return ;
1534
            }
1536
            public boolean isEmpty() {
1537
                TreeMap.Entry<K,V> n = absLowest();
1538
                return n == null || tooHigh(n.key);
1539
            }
1541
            public boolean contains(Object o) {
1542
                if (!(o instanceof Map.Entry))
1543
                    return false;
1544
                Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1545
                K key = entry.getKey();
1546
                if (!inRange(key))
1547
                    return false;
1548
                TreeMap.Entry node = .getEntry(key);
1549
                return node != null &&
1550
                    valEquals(node.getValue(), entry.getValue());
1551
            }
1553
            public boolean remove(Object o) {
1554
                if (!(o instanceof Map.Entry))
1555
                    return false;
1556
                Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1557
                K key = entry.getKey();
1558
                if (!inRange(key))
1559
                    return false;
1560
                TreeMap.Entry<K,V> node = .getEntry(key);
1561
                if (node!=null && valEquals(node.getValue(),entry.getValue())){
1562
                    .deleteEntry(node);
1563
                    return true;
1564
                }
1565
                return false;
1566
            }
1567
        }

        
Iterators for SubMaps 
1572
        abstract class SubMapIterator<T> implements Iterator<T> {
1573
            TreeMap.Entry<K,V> lastReturned;
1574
            TreeMap.Entry<K,V> next;
1575
            final Object fenceKey;
1576
            int expectedModCount;
1578
            SubMapIterator(TreeMap.Entry<K,V> first,
1579
                           TreeMap.Entry<K,V> fence) {
1580
                 = .;
1581
                 = null;
1582
                 = first;
1583
                 = fence == null ?  : fence.key;
1584
            }
1586
            public final boolean hasNext() {
1587
                return  != null && . != ;
1588
            }
1590
            final TreeMap.Entry<K,V> nextEntry() {
1591
                TreeMap.Entry<K,V> e = ;
1592
                if (e == null || e.key == )
1593
                    throw new NoSuchElementException();
1594
                if (. != )
1595
                    throw new ConcurrentModificationException();
1596
                 = successor(e);
1597
                 = e;
1598
                return e;
1599
            }
1601
            final TreeMap.Entry<K,V> prevEntry() {
1602
                TreeMap.Entry<K,V> e = ;
1603
                if (e == null || e.key == )
1604
                    throw new NoSuchElementException();
1605
                if (. != )
1606
                    throw new ConcurrentModificationException();
1607
                 = predecessor(e);
1608
                 = e;
1609
                return e;
1610
            }
1612
            final void removeAscending() {
1613
                if ( == null)
1614
                    throw new IllegalStateException();
1615
                if (. != )
1616
                    throw new ConcurrentModificationException();
1617
                // deleted entries are replaced by their successors
1618
                if (. != null && . != null)
1619
                     = ;
1620
                .deleteEntry();
1621
                 = null;
1622
                 = .;
1623
            }
1625
            final void removeDescending() {
1626
                if ( == null)
1627
                    throw new IllegalStateException();
1628
                if (. != )
1629
                    throw new ConcurrentModificationException();
1630
                .deleteEntry();
1631
                 = null;
1632
                 = .;
1633
            }
1635
        }
1637
        final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1638
            SubMapEntryIterator(TreeMap.Entry<K,V> first,
1639
                                TreeMap.Entry<K,V> fence) {
1640
                super(first, fence);
1641
            }
1642
            public Map.Entry<K,V> next() {
1643
                return nextEntry();
1644
            }
1645
            public void remove() {
1646
                removeAscending();
1647
            }
1648
        }
1650
        final class SubMapKeyIterator extends SubMapIterator<K> {
1651
            SubMapKeyIterator(TreeMap.Entry<K,V> first,
1652
                              TreeMap.Entry<K,V> fence) {
1653
                super(first, fence);
1654
            }
1655
            public K next() {
1656
                return nextEntry().;
1657
            }
1658
            public void remove() {
1659
                removeAscending();
1660
            }
1661
        }
1663
        final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1664
            DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1665
                                          TreeMap.Entry<K,V> fence) {
1666
                super(last, fence);
1667
            }
1669
            public Map.Entry<K,V> next() {
1670
                return prevEntry();
1671
            }
1672
            public void remove() {
1673
                removeDescending();
1674
            }
1675
        }
1677
        final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1678
            DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1679
                                        TreeMap.Entry<K,V> fence) {
1680
                super(last, fence);
1681
            }
1682
            public K next() {
1683
                return prevEntry().;
1684
            }
1685
            public void remove() {
1686
                removeDescending();
1687
            }
1688
        }
1689
    }

    

Serial:
include
1694
    static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1695
        private static final long serialVersionUID = 912986545866124060L;
1697
        AscendingSubMap(TreeMap<K,V> m,
1698
                        boolean fromStart, K lo, boolean loInclusive,
1699
                        boolean toEnd,     K hi, boolean hiInclusive) {
1700
            super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1701
        }
1703
        public Comparator<? super K> comparator() {
1704
            return .comparator();
1705
        }
1707
        public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1708
                                        K toKey,   boolean toInclusive) {
1709
            if (!inRange(fromKey, fromInclusive))
1710
                throw new IllegalArgumentException("fromKey out of range");
1711
            if (!inRange(toKey, toInclusive))
1712
                throw new IllegalArgumentException("toKey out of range");
1713
            return new AscendingSubMap(,
1714
                                       false, fromKey, fromInclusive,
1715
                                       false, toKey,   toInclusive);
1716
        }
1718
        public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1719
            if (!inRange(toKey, inclusive))
1720
                throw new IllegalArgumentException("toKey out of range");
1721
            return new AscendingSubMap(,
1722
                                       , ,    ,
1723
                                       false,     toKey, inclusive);
1724
        }
1726
        public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1727
            if (!inRange(fromKey, inclusive))
1728
                throw new IllegalArgumentException("fromKey out of range");
1729
            return new AscendingSubMap(,
1730
                                       false, fromKey, inclusive,
1731
                                       , ,      );
1732
        }
1734
        public NavigableMap<K,V> descendingMap() {
1735
            NavigableMap<K,V> mv = ;
1736
            return (mv != null) ? mv :
1737
                ( =
1738
                 new DescendingSubMap(,
1739
                                      , , ,
1740
                                      ,     , ));
1741
        }
1743
        Iterator<K> keyIterator() {
1744
            return new SubMapKeyIterator(absLowest(), absHighFence());
1745
        }
1747
        Iterator<K> descendingKeyIterator() {
1748
            return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1749
        }
1751
        final class AscendingEntrySetView extends EntrySetView {
1752
            public Iterator<Map.Entry<K,V>> iterator() {
1753
                return new SubMapEntryIterator(absLowest(), absHighFence());
1754
            }
1755
        }
1757
        public Set<Map.Entry<K,V>> entrySet() {
1758
            EntrySetView es = ;
1759
            return (es != null) ? es : new AscendingEntrySetView();
1760
        }
1762
        TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
1763
        TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
1764
        TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1765
        TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
1766
        TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
1767
        TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
1768
    }

    

Serial:
include
1773
    static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
1774
        private static final long serialVersionUID = 912986545866120460L;
1775
        DescendingSubMap(TreeMap<K,V> m,
1776
                        boolean fromStart, K lo, boolean loInclusive,
1777
                        boolean toEnd,     K hi, boolean hiInclusive) {
1778
            super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1779
        }
1781
        private final Comparator<? super K> reverseComparator =
1782
            Collections.reverseOrder(.);
1784
        public Comparator<? super K> comparator() {
1785
            return ;
1786
        }
1788
        public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1789
                                        K toKey,   boolean toInclusive) {
1790
            if (!inRange(fromKey, fromInclusive))
1791
                throw new IllegalArgumentException("fromKey out of range");
1792
            if (!inRange(toKey, toInclusive))
1793
                throw new IllegalArgumentException("toKey out of range");
1794
            return new DescendingSubMap(,
1795
                                        false, toKey,   toInclusive,
1796
                                        false, fromKey, fromInclusive);
1797
        }
1799
        public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1800
            if (!inRange(toKey, inclusive))
1801
                throw new IllegalArgumentException("toKey out of range");
1802
            return new DescendingSubMap(,
1803
                                        false, toKey, inclusive,
1804
                                        , ,    );
1805
        }
1807
        public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1808
            if (!inRange(fromKey, inclusive))
1809
                throw new IllegalArgumentException("fromKey out of range");
1810
            return new DescendingSubMap(,
1811
                                        , , ,
1812
                                        false, fromKey, inclusive);
1813
        }
1815
        public NavigableMap<K,V> descendingMap() {
1816
            NavigableMap<K,V> mv = ;
1817
            return (mv != null) ? mv :
1818
                ( =
1819
                 new AscendingSubMap(,
1820
                                     , , ,
1821
                                     ,     , ));
1822
        }
1824
        Iterator<K> keyIterator() {
1825
            return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1826
        }
1828
        Iterator<K> descendingKeyIterator() {
1829
            return new SubMapKeyIterator(absLowest(), absHighFence());
1830
        }
1832
        final class DescendingEntrySetView extends EntrySetView {
1833
            public Iterator<Map.Entry<K,V>> iterator() {
1834
                return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1835
            }
1836
        }
1838
        public Set<Map.Entry<K,V>> entrySet() {
1839
            EntrySetView es = ;
1840
            return (es != null) ? es : new DescendingEntrySetView();
1841
        }
1843
        TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
1844
        TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
1845
        TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1846
        TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
1847
        TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
1848
        TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
1849
    }

    
This class exists solely for the sake of serialization compatibility with previous releases of TreeMap that did not support NavigableMap. It translates an old-version SubMap into a new-version AscendingSubMap. This class is never otherwise used.

Serial:
include
1860
    private class SubMap extends AbstractMap<K,V>
1861
        implements SortedMap<K,V>, java.io.Serializable {
1862
        private static final long serialVersionUID = -6520786458950516097L;
1863
        private boolean fromStart = false, toEnd = false;
1864
        private K fromKey, toKey;
1865
        private Object readResolve() {
1866
            return new AscendingSubMap(TreeMap.this,
1867
                                       , , true,
1868
                                       , , false);
1869
        }
1870
        public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1871
        public K lastKey() { throw new InternalError(); }
1872
        public K firstKey() { throw new InternalError(); }
1873
        public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1874
        public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1875
        public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1876
        public Comparator<? super K> comparator() { throw new InternalError(); }
1877
    }
1880
    // Red-black mechanics
1882
    private static final boolean RED   = false;
1883
    private static final boolean BLACK = true;

    
Node in the Tree. Doubles as a means to pass key-value pairs back to user (see Map.Entry). 
1890
    static final class Entry<K,V> implements Map.Entry<K,V> {
1891
        K key;
1892
        V value;
1893
        Entry<K,V> left = null;
1894
        Entry<K,V> right = null;
1895
        Entry<K,V> parent;
1896
        boolean color = ;

        
Make a new cell with given key, value, and parent, and with null child links, and BLACK color. 
1902
        Entry(K key, V value, Entry<K,V> parent) {
1903
            this. = key;
1904
            this. = value;
1905
            this. = parent;
1906
        }

        
Returns the key.

Returns:
the key
1913
        public K getKey() {
1914
            return ;
1915
        }

        
Returns the value associated with the key.

Returns:
the value associated with the key
1922
        public V getValue() {
1923
            return ;
1924
        }

        
Replaces the value currently associated with the key with the given value.

Returns:
the value associated with the key before this method was called
1933
        public V setValue(V value) {
1934
            V oldValue = this.;
1935
            this. = value;
1936
            return oldValue;
1937
        }
1939
        public boolean equals(Object o) {
1940
            if (!(o instanceof Map.Entry))
1941
                return false;
1942
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1944
            return valEquals(,e.getKey()) && valEquals(,e.getValue());
1945
        }
1947
        public int hashCode() {
1948
            int keyHash = (==null ? 0 : .hashCode());
1949
            int valueHash = (==null ? 0 : .hashCode());
1950
            return keyHash ^ valueHash;
1951
        }
1953
        public String toString() {
1954
            return  + "=" + ;
1955
        }
1956
    }

    
Returns the first Entry in the TreeMap (according to the TreeMap's key-sort function). Returns null if the TreeMap is empty. 
1962
    final Entry<K,V> getFirstEntry() {
1963
        Entry<K,V> p = ;
1964
        if (p != null)
1965
            while (p.left != null)
1966
                p = p.left;
1967
        return p;
1968
    }

    
Returns the last Entry in the TreeMap (according to the TreeMap's key-sort function). Returns null if the TreeMap is empty. 
1974
    final Entry<K,V> getLastEntry() {
1975
        Entry<K,V> p = ;
1976
        if (p != null)
1977
            while (p.right != null)
1978
                p = p.right;
1979
        return p;
1980
    }

    
Returns the successor of the specified Entry, or null if no such. 
1985
    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1986
        if (t == null)
1987
            return null;
1988
        else if (t.right != null) {
1989
            Entry<K,V> p = t.right;
1990
            while (p.left != null)
1991
                p = p.left;
1992
            return p;
1993
        } else {
1994
            Entry<K,V> p = t.parent;
1995
            Entry<K,V> ch = t;
1996
            while (p != null && ch == p.right) {
1997
                ch = p;
1998
                p = p.parent;
1999
            }
2000
            return p;
2001
        }
2002
    }

    
Returns the predecessor of the specified Entry, or null if no such. 
2007
    static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2008
        if (t == null)
2009
            return null;
2010
        else if (t.left != null) {
2011
            Entry<K,V> p = t.left;
2012
            while (p.right != null)
2013
                p = p.right;
2014
            return p;
2015
        } else {
2016
            Entry<K,V> p = t.parent;
2017
            Entry<K,V> ch = t;
2018
            while (p != null && ch == p.left) {
2019
                ch = p;
2020
                p = p.parent;
2021
            }
2022
            return p;
2023
        }
2024
    }

    
Balancing operations. Implementations of rebalancings during insertion and deletion are slightly different than the CLR version. Rather than using dummy nilnodes, we use a set of accessors that deal properly with null. They are used to avoid messiness surrounding nullness checks in the main algorithms. 
2036
    private static <K,V> boolean colorOf(Entry<K,V> p) {
2037
        return (p == null ?  : p.color);
2038
    }
2040
    private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
2041
        return (p == null ? null: p.parent);
2042
    }
2044
    private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2045
        if (p != null)
2046
            p.color = c;
2047
    }
2049
    private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
2050
        return (p == null) ? null: p.left;
2051
    }
2053
    private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
2054
        return (p == null) ? null: p.right;
2055
    }

    
From CLR
2058
    private void rotateLeft(Entry<K,V> p) {
2059
        if (p != null) {
2060
            Entry<K,V> r = p.right;
2061
            p.right = r.left;
2062
            if (r.left != null)
2063
                r.left.parent = p;
2064
            r.parent = p.parent;
2065
            if (p.parent == null)
2066
                 = r;
2067
            else if (p.parent.left == p)
2068
                p.parent.left = r;
2069
            else
2070
                p.parent.right = r;
2071
            r.left = p;
2072
            p.parent = r;
2073
        }
2074
    }

    
From CLR
2077
    private void rotateRight(Entry<K,V> p) {
2078
        if (p != null) {
2079
            Entry<K,V> l = p.left;
2080
            p.left = l.right;
2081
            if (l.right != null) l.right.parent = p;
2082
            l.parent = p.parent;
2083
            if (p.parent == null)
2084
                 = l;
2085
            else if (p.parent.right == p)
2086
                p.parent.right = l;
2087
            else p.parent.left = l;
2088
            l.right = p;
2089
            p.parent = l;
2090
        }
2091
    }

    
From CLR
2094
    private void fixAfterInsertion(Entry<K,V> x) {
2095
        x.color = ;
2097
        while (x != null && x !=  && x.parent.color == ) {
2098
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2099
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
2100
                if (colorOf(y) == ) {
2101
                    setColor(parentOf(x), );
2102
                    setColor(y, );
2103
                    setColor(parentOf(parentOf(x)), );
2104
                    x = parentOf(parentOf(x));
2105
                } else {
2106
                    if (x == rightOf(parentOf(x))) {
2107
                        x = parentOf(x);
2108
                        rotateLeft(x);
2109
                    }
2110
                    setColor(parentOf(x), );
2111
                    setColor(parentOf(parentOf(x)), );
2112
                    rotateRight(parentOf(parentOf(x)));
2113
                }
2114
            } else {
2115
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
2116
                if (colorOf(y) == ) {
2117
                    setColor(parentOf(x), );
2118
                    setColor(y, );
2119
                    setColor(parentOf(parentOf(x)), );
2120
                    x = parentOf(parentOf(x));
2121
                } else {
2122
                    if (x == leftOf(parentOf(x))) {
2123
                        x = parentOf(x);
2124
                        rotateRight(x);
2125
                    }
2126
                    setColor(parentOf(x), );
2127
                    setColor(parentOf(parentOf(x)), );
2128
                    rotateLeft(parentOf(parentOf(x)));
2129
                }
2130
            }
2131
        }
2132
        . = ;
2133
    }

    
Delete node p, and then rebalance the tree. 
2138
    private void deleteEntry(Entry<K,V> p) {
2139
        ++;
2140
        --;
2142
        // If strictly internal, copy successor's element to p and then make p
2143
        // point to successor.
2144
        if (p.left != null && p.right != null) {
2145
            Entry<K,V> s = successor (p);
2146
            p.key = s.key;
2147
            p.value = s.value;
2148
            p = s;
2149
        } // p has 2 children
2151
        // Start fixup at replacement node, if it exists.
2152
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2154
        if (replacement != null) {
2155
            // Link replacement to parent
2156
            replacement.parent = p.parent;
2157
            if (p.parent == null)
2158
                 = replacement;
2159
            else if (p == p.parent.left)
2160
                p.parent.left  = replacement;
2161
            else
2162
                p.parent.right = replacement;
2164
            // Null out links so they are OK to use by fixAfterDeletion.
2165
            p.left = p.right = p.parent = null;
2167
            // Fix replacement
2168
            if (p.color == )
2169
                fixAfterDeletion(replacement);
2170
        } else if (p.parent == null) { // return if we are the only node.
2171
             = null;
2172
        } else { //  No children. Use self as phantom replacement and unlink.
2173
            if (p.color == )
2174
                fixAfterDeletion(p);
2176
            if (p.parent != null) {
2177
                if (p == p.parent.left)
2178
                    p.parent.left = null;
2179
                else if (p == p.parent.right)
2180
                    p.parent.right = null;
2181
                p.parent = null;
2182
            }
2183
        }
2184
    }

    
From CLR
2187
    private void fixAfterDeletion(Entry<K,V> x) {
2188
        while (x !=  && colorOf(x) == ) {
2189
            if (x == leftOf(parentOf(x))) {
2190
                Entry<K,V> sib = rightOf(parentOf(x));
2192
                if (colorOf(sib) == ) {
2193
                    setColor(sib, );
2194
                    setColor(parentOf(x), );
2195
                    rotateLeft(parentOf(x));
2196
                    sib = rightOf(parentOf(x));
2197
                }
2199
                if (colorOf(leftOf(sib))  ==  &&
2200
                    colorOf(rightOf(sib)) == ) {
2201
                    setColor(sib, );
2202
                    x = parentOf(x);
2203
                } else {
2204
                    if (colorOf(rightOf(sib)) == ) {
2205
                        setColor(leftOf(sib), );
2206
                        setColor(sib, );
2207
                        rotateRight(sib);
2208
                        sib = rightOf(parentOf(x));
2209
                    }
2210
                    setColor(sib, colorOf(parentOf(x)));
2211
                    setColor(parentOf(x), );
2212
                    setColor(rightOf(sib), );
2213
                    rotateLeft(parentOf(x));
2214
                    x = ;
2215
                }
2216
            } else { // symmetric
2217
                Entry<K,V> sib = leftOf(parentOf(x));
2219
                if (colorOf(sib) == ) {
2220
                    setColor(sib, );
2221
                    setColor(parentOf(x), );
2222
                    rotateRight(parentOf(x));
2223
                    sib = leftOf(parentOf(x));
2224
                }
2226
                if (colorOf(rightOf(sib)) ==  &&
2227
                    colorOf(leftOf(sib)) == ) {
2228
                    setColor(sib, );
2229
                    x = parentOf(x);
2230
                } else {
2231
                    if (colorOf(leftOf(sib)) == ) {
2232
                        setColor(rightOf(sib), );
2233
                        setColor(sib, );
2234
                        rotateLeft(sib);
2235
                        sib = leftOf(parentOf(x));
2236
                    }
2237
                    setColor(sib, colorOf(parentOf(x)));
2238
                    setColor(parentOf(x), );
2239
                    setColor(leftOf(sib), );
2240
                    rotateRight(parentOf(x));
2241
                    x = ;
2242
                }
2243
            }
2244
        }
2246
        setColor(x, );
2247
    }
2249
    private static final long serialVersionUID = 919286545866124006L;

    
Save the state of the TreeMap instance to a stream (i.e., serialize it).

SerialData:
The size of the TreeMap (the number of key-value mappings) is emitted (int), followed by the key (Object) and value (Object) for each key-value mapping represented by the TreeMap. The key-value mappings are emitted in key-order (as determined by the TreeMap's Comparator, or by the keys' natural ordering if the TreeMap has no Comparator).
2263
    private void writeObject(java.io.ObjectOutputStream s)
2264
        throws java.io.IOException {
2265
        // Write out the Comparator and any hidden stuff
2266
        s.defaultWriteObject();
2268
        // Write out size (number of Mappings)
2269
        s.writeInt();
2271
        // Write out keys and values (alternating)
2272
        for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2273
            Map.Entry<K,V> e = i.next();
2274
            s.writeObject(e.getKey());
2275
            s.writeObject(e.getValue());
2276
        }
2277
    }

    
Reconstitute the TreeMap instance from a stream (i.e., deserialize it). 
2283
    private void readObject(final java.io.ObjectInputStream s)
2284
        throws java.io.IOException, ClassNotFoundException {
2285
        // Read in the Comparator and any hidden stuff
2286
        s.defaultReadObject();
2288
        // Read in size
2289
        int size = s.readInt();
2291
        buildFromSorted(size, null, s, null);
2292
    }

    
Intended to be called only from TreeSet.readObject
2295
    void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2296
        throws java.io.IOException, ClassNotFoundException {
2297
        buildFromSorted(size, null, s, defaultVal);
2298
    }

    
Intended to be called only from TreeSet.addAll
2301
    void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2302
        try {
2303
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2304
        } catch (java.io.IOException cannotHappen) {
2305
        } catch (ClassNotFoundException cannotHappen) {
2306
        }
2307
    }


    
Linear time tree building algorithm from sorted data. Can accept keys and/or values from iterator or stream. This leads to too many parameters, but seems better than alternatives. The four formats that this method accepts are: 1) An iterator of Map.Entries. (it != null, defaultVal == null). 2) An iterator of keys. (it != null, defaultVal != null). 3) A stream of alternating serialized keys and values. (it == null, defaultVal == null). 4) A stream of serialized keys. (it == null, defaultVal != null). It is assumed that the comparator of the TreeMap is already set prior to calling this method.

Parameters:
size the number of keys (or key-value pairs) to be read from the iterator or stream
it If non-null, new entries are created from entries or keys read from this iterator.
str If non-null, new entries are created from keys and possibly values read from this stream in serialized form. Exactly one of it and str should be non-null.
defaultVal if non-null, this default value is used for each value in the map. If null, each value is read from iterator or stream, as described above.
Throws:
IOException propagated from stream reads. This cannot occur if str is null.
java.lang.ClassNotFoundException propagated from readObject. This cannot occur if str is null.
2340
    private void buildFromSorted(int size, Iterator it,
2341
                                 java.io.ObjectInputStream str,
2342
                                 V defaultVal)
2343
        throws  java.io.IOException, ClassNotFoundException {
2344
        this. = size;
2345
         = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2346
                               it, str, defaultVal);
2347
    }

    
Recursive "helper method" that does the real work of the previous method. Identically named parameters have identical definitions. Additional parameters are documented below. It is assumed that the comparator and size fields of the TreeMap are already set prior to calling this method. (It ignores both fields.)

Parameters:
level the current level of tree. Initial call should be 0.
lo the first element index of this subtree. Initial should be 0.
hi the last element index of this subtree. Initial should be size-1.
redLevel the level at which nodes should be red. Must be equal to computeRedLevel for tree of this size.
2363
    private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2364
                                             int redLevel,
2365
                                             Iterator it,
2366
                                             java.io.ObjectInputStream str,
2367
                                             V defaultVal)
2368
        throws  java.io.IOException, ClassNotFoundException {
2369
        /*
2370
         * Strategy: The root is the middlemost element. To get to it, we
2371
         * have to first recursively construct the entire left subtree,
2372
         * so as to grab all of its elements. We can then proceed with right
2373
         * subtree.
2374
         *
2375
         * The lo and hi arguments are the minimum and maximum
2376
         * indices to pull out of the iterator or stream for current subtree.
2377
         * They are not actually indexed, we just proceed sequentially,
2378
         * ensuring that items are extracted in corresponding order.
2379
         */
2381
        if (hi < lo) return null;
2383
        int mid = (lo + hi) >>> 1;
2385
        Entry<K,V> left  = null;
2386
        if (lo < mid)
2387
            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2388
                                   it, str, defaultVal);
2390
        // extract key and/or value from iterator or stream
2391
        K key;
2392
        V value;
2393
        if (it != null) {
2394
            if (defaultVal==null) {
2395
                Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
2396
                key = entry.getKey();
2397
                value = entry.getValue();
2398
            } else {
2399
                key = (K)it.next();
2400
                value = defaultVal;
2401
            }
2402
        } else { // use stream
2403
            key = (K) str.readObject();
2404
            value = (defaultVal != null ? defaultVal : (V) str.readObject());
2405
        }
2407
        Entry<K,V> middle =  new Entry<K,V>(key, value, null);
2409
        // color nodes in non-full bottommost level red
2410
        if (level == redLevel)
2411
            middle.color = ;
2413
        if (left != null) {
2414
            middle.left = left;
2415
            left.parent = middle;
2416
        }
2418
        if (mid < hi) {
2419
            Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2420
                                               it, str, defaultVal);
2421
            middle.right = right;
2422
            right.parent = middle;
2423
        }
2425
        return middle;
2426
    }

    
Find the level down to which to assign all nodes BLACK. This is the last `full' level of the complete binary tree produced by buildTree. The remaining nodes are colored RED. (This makes a `nice' set of color assignments wrt future insertions.) This level number is computed by finding the number of splits needed to reach the zeroeth node. (The answer is ~lg(N), but in any case must be computed by same quick O(lg(N)) loop.) 
2437
    private static int computeRedLevel(int sz) {
2438
        int level = 0;
2439
        for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2440
            level++;
2441
        return level;
2442
    }
New to GrepCode? Check out our FAQ X