aboutsummaryrefslogtreecommitdiff
path: root/libjava/java/io/RandomAccessFile.java
blob: 990b2dcb5bdd2dd83c36c377ff1b8b1ee341949c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
/* RandomAccessFile.java -- Class supporting random file I/O
   Copyright (C) 1998, 1999, 2001, 2002, 2003 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
 
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.io;

import java.nio.channels.FileChannel;
import gnu.java.nio.FileChannelImpl;

/* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
 * "The Java Language Specification", ISBN 0-201-63451-1
 * Status: Believe complete and correct to 1.1.
 */

/**
 * This class allows reading and writing of files at random locations.
 * Most Java I/O classes are either pure sequential input or output.  This
 * class fulfills the need to be able to read the bytes of a file in an
 * arbitrary order.  In addition, this class implements the
 * <code>DataInput</code> and <code>DataOutput</code> interfaces to allow
 * the reading and writing of Java primitives.
 *
 * @author Aaron M. Renn <arenn@urbanophile.com>
 * @author Tom Tromey <tromey@cygnus.com>
 */
public class RandomAccessFile implements DataOutput, DataInput
{

  // The underlying file.
  private FileDescriptor fd;
  // The corresponding input and output streams.
  private DataOutputStream out;
  private DataInputStream in;
  
  private FileChannel ch; /* cached associated file-channel */
  
  /**
   * This method initializes a new instance of <code>RandomAccessFile</code>
   * to read from the specified <code>File</code> object with the specified 
   * access mode.   The access mode is either "r" for read only access or "rw" 
   * for read-write access.
   * <p>
   * Note that a <code>SecurityManager</code> check is made prior to
   * opening the file to determine whether or not this file is allowed to
   * be read or written.
   *
   * @param file The <code>File</code> object to read and/or write.
   * @param mode "r" for read only or "rw" for read-write access to the file
   *
   * @exception IllegalArgumentException If <code>mode</code> has an 
   * illegal value
   * @exception SecurityException If the requested access to the file 
   * is not allowed
   * @exception IOException If any other error occurs
   */
  public RandomAccessFile (File file, String mode)
    throws FileNotFoundException
  {
    this (file.getPath(), mode);
  }

  /**
   * This method initializes a new instance of <code>RandomAccessFile</code>
   * to read from the specified file name with the specified access mode.
   * The access mode is either "r" for read only access or "rw" for read
   * write access.
   * <p>
   * Note that a <code>SecurityManager</code> check is made prior to
   * opening the file to determine whether or not this file is allowed to
   * be read or written.
   *
   * @param fileName The name of the file to read and/or write
   * @param mode "r" for read only or "rw" for read-write access to the file
   *
   * @exception IllegalArgumentException If <code>mode</code> has an 
   * illegal value
   * @exception SecurityException If the requested access to the file 
   * is not allowed
   * @exception FileNotFoundException If any other error occurs
   */
  public RandomAccessFile (String fileName, String mode)
    throws FileNotFoundException
  {
    // Check the mode
    if (!mode.equals("r") && !mode.equals("rw") && !mode.equals("rws") &&
        !mode.equals("rwd"))
      throw new IllegalArgumentException("Bad mode value: " + mode);
  
    int fdmode;
    if (mode.compareTo ("r") == 0)
      fdmode = FileDescriptor.READ;
    else if (mode.compareTo ("rw") == 0)
      fdmode = FileDescriptor.READ | FileDescriptor.WRITE;
    else
      throw new IllegalArgumentException ("invalid mode: " + mode);

    // The obligatory SecurityManager stuff
    SecurityManager s = System.getSecurityManager();
    if (s != null)
      {
        s.checkRead(fileName);

        if ((fdmode & FileDescriptor.WRITE) != 0)
          s.checkWrite(fileName);
      }

    fd = new FileDescriptor (fileName, fdmode);
    out = new DataOutputStream (new FileOutputStream (fd));
    in = new DataInputStream (new FileInputStream (fd));
  }

  /**
   * This method closes the file and frees up all file related system
   * resources.  Since most operating systems put a limit on how many files
   * may be opened at any given time, it is a good idea to close all files
   * when no longer needed to avoid hitting this limit
   */
  public void close () throws IOException
  {
    if (fd.valid())
      fd.close();
  }

  /**
   * This method returns a <code>FileDescriptor</code> object that 
   * represents the native file handle for this file.
   *
   * @return The <code>FileDescriptor</code> object for this file
   *
   * @exception IOException If an error occurs
   */
  public final FileDescriptor getFD () throws IOException
  {
    if (! fd.valid())
      throw new IOException ();

    return fd;
  }

  /**
   * This method returns the current offset in the file at which the next
   * read or write will occur
   *
   * @return The current file position
   *
   * @exception IOException If an error occurs
   */
  public long getFilePointer () throws IOException
  {
    return fd.getFilePointer();
  }

  /**
   * This method sets the length of the file to the specified length.  If
   * the currently length of the file is longer than the specified length,
   * then the file is truncated to the specified length.  If the current
   * length of the file is shorter than the specified length, the file
   * is extended with bytes of an undefined value.
   *  <p>
   * The file must be open for write access for this operation to succeed.
   *
   * @param newlen The new length of the file
   *
   * @exception IOException If an error occurs
   */
  public void setLength (long pos) throws IOException
  {
    fd.setLength(pos);
  }

  /**
   * This method returns the length of the file in bytes
   *
   * @return The length of the file
   *
   * @exception IOException If an error occurs
   */
  public long length () throws IOException
  {
    return fd.length();
  }

  /**
   * This method reads a single byte of data from the file and returns it
   * as an integer.
   *
   * @return The byte read as an int, or -1 if the end of the file was reached.
   *
   * @exception IOException If an error occurs
   */
  public int read () throws IOException
  {
    return in.read();
  }

  /**
   * This method reads bytes from the file into the specified array.  The
   * bytes are stored starting at the beginning of the array and up to 
   * <code>buf.length</code> bytes can be read.
   *
   * @param buf The buffer to read bytes from the file into
   *
   * @return The actual number of bytes read or -1 if end of file
   *
   * @exception IOException If an error occurs
   */
  public int read (byte[] buffer) throws IOException
  {
    return in.read (buffer);
  }

  /**
   * This methods reads up to <code>len</code> bytes from the file into the
   * specified array starting at position <code>offset</code> into the array.
   *
   * @param buf The array to read the bytes into
   * @param offset The index into the array to start storing bytes
   * @param len The requested number of bytes to read
   *
   * @return The actual number of bytes read, or -1 if end of file
   *
   * @exception IOException If an error occurs
   */
  public int read (byte[] buffer, int offset, int len) throws IOException
  {
    return in.read (buffer, offset, len);
  }

  /**
   * This method reads a Java boolean value from an input stream.  It does
   * so by reading a single byte of data.  If that byte is zero, then the
   * value returned is <code>false</code>  If the byte is non-zero, then
   * the value returned is <code>true</code>
   * <p>
   * This method can read a <code>boolean</code> written by an object 
   * implementing the
   * <code>writeBoolean()</code> method in the <code>DataOutput</code> 
   * interface.
   *
   * @return The <code>boolean</code> value read
   *
   * @exception EOFException If end of file is reached before reading the 
   * boolean
   * @exception IOException If any other error occurs
   */
  public final boolean readBoolean () throws IOException
  {
    return in.readBoolean ();
  }

  /**
   * This method reads a Java byte value from an input stream.  The value
   * is in the range of -128 to 127.
   * <p>
   * This method can read a <code>byte</code> written by an object 
   * implementing the 
   * <code>writeByte()</code> method in the <code>DataOutput</code> interface.
   *
   * @return The <code>byte</code> value read
   *
   * @exception EOFException If end of file is reached before reading the byte
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final byte readByte () throws IOException
  {
    return in.readByte ();
  }

  /**
   * This method reads a Java <code>char</code> value from an input stream.  
   * It operates by reading two bytes from the stream and converting them to 
   * a single 16-bit Java <code>char</code>  The two bytes are stored most
   * significant byte first (i.e., "big endian") regardless of the native
   * host byte ordering. 
   * <p>
   * As an example, if <code>byte1</code> and code{byte2</code> represent 
   * the first
   * and second byte read from the stream respectively, they will be
   * transformed to a <code>char</code> in the following manner:
   * <p>
   * <code>(char)(((byte1 & 0xFF) << 8) | (byte2 & 0xFF)</code>
   * <p>
   * This method can read a <code>char</code> written by an object 
   * implementing the
   * <code>writeChar()</code> method in the <code>DataOutput</code> interface.
   *
   * @return The <code>char</code> value read 
   *
   * @exception EOFException If end of file is reached before reading the char
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final char readChar () throws IOException
  {
    return in.readChar();
  }

  /**
   * This method reads a Java double value from an input stream.  It operates
   * by first reading a <code>logn</code> value from the stream by calling the
   * <code>readLong()</code> method in this interface, then 
   * converts that <code>long</code>
   * to a <code>double</code> using the <code>longBitsToDouble</code> 
   * method in the class <code>java.lang.Double</code>
   * <p>
   * This method can read a <code>double</code> written by an object 
   * implementing the
   * <code>writeDouble()</code> method in the <code>DataOutput</code> 
   * interface.
   *
   * @return The <code>double</code> value read
   *
   * @exception EOFException If end of file is reached before reading 
   * the double
   * @exception IOException If any other error occurs
   *
   * @see java.lang.Double
   * @see DataOutput
   */
  public final double readDouble () throws IOException
  {
    return in.readDouble ();
  }

  /**
   * This method reads a Java float value from an input stream.  It operates
   * by first reading an <code>int</code> value from the stream by calling the
   * <code>readInt()</code> method in this interface, then converts 
   * that <code>int</code>
   * to a <code>float</code> using the <code>intBitsToFloat</code> method in 
   * the class <code>java.lang.Float</code>
   * <p>
   * This method can read a <code>float</code> written by an object 
   * implementing the
   * <code>writeFloat()</code> method in the <code>DataOutput</code> interface.
   *
   * @return The <code>float</code> value read
   *
   * @exception EOFException If end of file is reached before reading the float
   * @exception IOException If any other error occurs
   *
   * @see java.lang.Float
   * @see DataOutput
   */
  public final float readFloat () throws IOException
  {
    return in.readFloat();
  }

  /**
   * This method reads raw bytes into the passed array until the array is
   * full.  Note that this method blocks until the data is available and
   * throws an exception if there is not enough data left in the stream to
   * fill the buffer
   *
   * @param buf The buffer into which to read the data
   *
   * @exception EOFException If end of file is reached before filling the 
   * buffer
   * @exception IOException If any other error occurs
   */
  public final void readFully (byte[] buffer) throws IOException
  {
    in.readFully(buffer);
  }

  /**
   * This method reads raw bytes into the passed array <code>buf</code> 
   * starting
   * <code>offset</code> bytes into the buffer.  The number of bytes read 
   * will be
   * exactly <code>len</code>  Note that this method blocks until the data is 
   * available and throws an exception if there is not enough data left in 
   * the stream to read <code>len</code> bytes.
   *
   * @param buf The buffer into which to read the data
   * @param offset The offset into the buffer to start storing data
   * @param len The number of bytes to read into the buffer
   *
   * @exception EOFException If end of file is reached before filling 
   * the buffer
   * @exception IOException If any other error occurs
   */
  public final void readFully (byte[] buffer, int offset, int count)
    throws IOException
  {
    in.readFully (buffer, offset, count);
  }

  /**
   * This method reads a Java <code>int</code> value from an input stream
   * It operates by reading four bytes from the stream and converting them to 
   * a single Java <code>int</code>  The bytes are stored most
   * significant byte first (i.e., "big endian") regardless of the native
   * host byte ordering. 
   * <p>
   * As an example, if <code>byte1</code> through <code>byte4</code> 
   * represent the first
   * four bytes read from the stream, they will be
   * transformed to an <code>int</code> in the following manner:
   * <p>
   * <code>(int)(((byte1 & 0xFF) << 24) + ((byte2 & 0xFF) << 16) + 
   * ((byte3 & 0xFF) << 8) + (byte4 & 0xFF)))</code>
   * <p>
   * The value returned is in the range of 0 to 65535.
   * <p>
   * This method can read an <code>int</code> written by an object 
   * implementing the
   * <code>writeInt()</code> method in the <code>DataOutput</code> interface.
   *
   * @return The <code>int</code> value read
   *
   * @exception EOFException If end of file is reached before reading the int
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final int readInt () throws IOException
  {
    return in.readInt();
  }

  /**
   * This method reads the next line of text data from an input stream.
   * It operates by reading bytes and converting those bytes to 
   * <code>char</code>
   * values by treating the byte read as the low eight bits of the 
   * <code>char</code>
   * and using <code>0</code> as the high eight bits.  Because of this, it does
   * not support the full 16-bit Unicode character set.
   * <p>
   * The reading of bytes ends when either the end of file or a line terminator
   * is encountered.  The bytes read are then returned as a <code>String</code>
   * A line terminator is a byte sequence consisting of either 
   * <code>\r</code> <code>\n</code> or <code>\r\n</code>  These 
   * termination charaters are
   * discarded and are not returned as part of the string.
   * <p>
   * This method can read data that was written by an object implementing the
   * <code>writeLine()</code> method in <code>DataOutput</code>
   *
   * @return The line read as a <code>String</code>
   *
   * @exception IOException If an error occurs
   *
   * @see DataOutput
   *
   * @deprecated
   */
  public final String readLine () throws IOException
  {
    return in.readLine ();
  }

  /**
   * This method reads a Java long value from an input stream
   * It operates by reading eight bytes from the stream and converting them to 
   * a single Java <code>long</code>  The bytes are stored most
   * significant byte first (i.e., "big endian") regardless of the native
   * host byte ordering. 
   * <p>
   * As an example, if <code>byte1</code> through <code>byte8</code> 
   * represent the first
   * eight bytes read from the stream, they will be
   * transformed to an <code>long</code> in the following manner:
   * <p>
   * <code>
   * (long)((((long)byte1 & 0xFF) << 56) + (((long)byte2 & 0xFF) << 48) + 
   * (((long)byte3 & 0xFF) << 40) + (((long)byte4 & 0xFF) << 32) + 
   * (((long)byte5 & 0xFF) << 24) + (((long)byte6 & 0xFF) << 16) + 
   * (((long)byte7 & 0xFF) << 8) + ((long)byte9 & 0xFF)))</code>
   * <p>
   * The value returned is in the range of 0 to 65535.
   * <p>
   * This method can read an <code>long</code> written by an object 
   * implementing the
   * <code>writeLong()</code> method in the <code>DataOutput</code> interface.
   *
   * @return The <code>long</code> value read
   *
   * @exception EOFException If end of file is reached before reading the long
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final long readLong () throws IOException
  {
    return in.readLong();
  }

  /**
   * This method reads a signed 16-bit value into a Java in from the stream.
   * It operates by reading two bytes from the stream and converting them to 
   * a single 16-bit Java <code>short</code>  The two bytes are stored most
   * significant byte first (i.e., "big endian") regardless of the native
   * host byte ordering. 
   * <p>
   * As an example, if <code>byte1</code> and code{byte2</code> 
   * represent the first
   * and second byte read from the stream respectively, they will be
   * transformed to a <code>short</code> in the following manner:
   * <p>
   * <code>(short)(((byte1 & 0xFF) << 8) | (byte2 & 0xFF)</code>
   * <p>
   * The value returned is in the range of -32768 to 32767.
   * <p>
   * This method can read a <code>short</code> written by an object 
   * implementing the
   * <code>writeShort()</code> method in the <code>DataOutput</code> interface.
   *
   * @return The <code>short</code> value read
   *
   * @exception EOFException If end of file is reached before reading the value
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final short readShort () throws IOException
  {
    return in.readShort();
  }

  /**
   * This method reads 8 unsigned bits into a Java <code>int</code> value 
   * from the 
   * stream. The value returned is in the range of 0 to 255.
   * <p>
   * This method can read an unsigned byte written by an object implementing 
   * the <code>writeUnsignedByte()</code> method in the 
   * <code>DataOutput</code> interface.
   *
   * @return The unsigned bytes value read as a Java <code>int</code>
   *
   * @exception EOFException If end of file is reached before reading the value
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final int readUnsignedByte () throws IOException
  {
    return in.readUnsignedByte();
  }

  /**
   * This method reads 16 unsigned bits into a Java int value from the stream.
   * It operates by reading two bytes from the stream and converting them to 
   * a single Java <code>int</code>  The two bytes are stored most
   * significant byte first (i.e., "big endian") regardless of the native
   * host byte ordering. 
   * <p>
   * As an example, if <code>byte1</code> and <code>byte2</code> 
   * represent the first
   * and second byte read from the stream respectively, they will be
   * transformed to an <code>int</code> in the following manner:
   * <p>
   * <code>(int)(((byte1 & 0xFF) << 8) + (byte2 & 0xFF))</code>
   * <p>
   * The value returned is in the range of 0 to 65535.
   * <p>
   * This method can read an unsigned short written by an object implementing
   * the <code>writeUnsignedShort()</code> method in the 
   * <code>DataOutput</code> interface.
   *
   * @return The unsigned short value read as a Java <code>int</code>
   *
   * @exception EOFException If end of file is reached before reading the value
   * @exception IOException If any other error occurs
   */
  public final int readUnsignedShort () throws IOException
  {
    return in.readUnsignedShort();
  }

  /**
   * This method reads a <code>String</code> from an input stream that 
   * is encoded in
   * a modified UTF-8 format.  This format has a leading two byte sequence
   * that contains the remaining number of bytes to read.  This two byte
   * sequence is read using the <code>readUnsignedShort()</code> method of this
   * interface.
   * <p>
   * After the number of remaining bytes have been determined, these bytes
   * are read an transformed into <code>char</code> values.  
   * These <code>char</code> values
   * are encoded in the stream using either a one, two, or three byte format.
   * The particular format in use can be determined by examining the first
   * byte read.  
   * <p>
   * If the first byte has a high order bit of 0 then
   * that character consists on only one byte.  This character value consists
   * of seven bits that are at positions 0 through 6 of the byte.  As an
   * example, if <code>byte1</code> is the byte read from the stream, it would
   * be converted to a <code>char</code> like so:
   * <p>
   * <code>(char)byte1</code>
   * <p>
   * If the first byte has <code>110</code> as its high order bits, then the 
   * character consists of two bytes.  The bits that make up the character
   * value are in positions 0 through 4 of the first byte and bit positions
   * 0 through 5 of the second byte.  (The second byte should have 
   * 10 as its high order bits).  These values are in most significant
   * byte first (i.e., "big endian") order.
   * <p>
   * As an example, if <code>byte1</code> and <code>byte2</code> 
   * are the first two bytes
   * read respectively, and the high order bits of them match the patterns
   * which indicate a two byte character encoding, then they would be
   * converted to a Java <code>char</code> like so:
   * <p>
   * <code>(char)(((byte1 & 0x1F) << 6) | (byte2 & 0x3F))</code>
   * <p>
   * If the first byte has a <code>1110</code> as its high order bits, then the
   * character consists of three bytes.  The bits that make up the character
   * value are in positions 0 through 3 of the first byte and bit positions
   * 0 through 5 of the other two bytes.  (The second and third bytes should
   * have <code>10</code> as their high order bits).  These values are in most
   * significant byte first (i.e., "big endian") order.
   * <p>
   * As an example, if <code>byte1</code> <code>byte2</code> 
   * and <code>byte3</code> are the
   * three bytes read, and the high order bits of them match the patterns
   * which indicate a three byte character encoding, then they would be
   * converted to a Java <code>char</code> like so:
   * <p>
   * <code>(char)(((byte1 & 0x0F) << 12) | ((byte2 & 0x3F) << 6) | 
   * (byte3 & 0x3F))</code>
   * <p>
   * Note that all characters are encoded in the method that requires the
   * fewest number of bytes with the exception of the character with the
   * value of <code>&#92;u0000</code> which is encoded as two bytes.  This is 
   * a  modification of the UTF standard used to prevent C language style
   * <code>NUL</code> values from appearing in the byte stream.
   * <p>
   * This method can read data that was written by an object implementing the
   * <code>writeUTF()</code> method in <code>DataOutput</code>
   * 
   * @return The <code>String</code> read
   *
   * @exception EOFException If end of file is reached before reading the 
   * String
   * @exception UTFDataFormatException If the data is not in UTF-8 format
   * @exception IOException If any other error occurs
   *
   * @see DataOutput
   */
  public final String readUTF () throws IOException
  {
    return in.readUTF();
  }

  /**
   * This method sets the current file position to the specified offset 
   * from the beginning of the file.  Note that some operating systems will
   * allow the file pointer to be set past the current end of the file.
   *
   * @param pos The offset from the beginning of the file at which to set 
   * the file pointer
   *
   * @exception IOException If an error occurs
   */
  public void seek (long pos) throws IOException
  {
    fd.seek (pos, FileDescriptor.SET, false);
  }

  /**
   * This method attempts to skip and discard the specified number of bytes 
   * in the input stream.  It may actually skip fewer bytes than requested. 
   * The actual number of bytes skipped is returned.  This method will not
   * skip any bytes if passed a negative number of bytes to skip.
   *
   * @param numBytes The requested number of bytes to skip.
   *
   * @return The number of bytes actually skipped.
   *
   * @exception IOException If an error occurs.
   */
  public int skipBytes (int numBytes) throws IOException
  {
    if (numBytes < 0)
      throw new IllegalArgumentException ("Can't skip negative bytes: " +
                                          numBytes);
    
    if (numBytes == 0)
      return 0;
    
    long curPos = fd.getFilePointer ();
    long newPos = fd.seek (numBytes, FileDescriptor.CUR, true);
    
    return (int) (newPos - curPos);
  }

  /**
   * This method writes a single byte of data to the file. The file must
   * be open for read-write in order for this operation to succeed.
   *
   * @param The byte of data to write, passed as an int.
   *
   * @exception IOException If an error occurs
   */
  public void write (int oneByte) throws IOException
  {
    out.write(oneByte);
  }

  /**
   * This method writes all the bytes in the specified array to the file.
   * The file must be open read-write in order for this operation to succeed.
   *
   * @param buf The array of bytes to write to the file
   */
  public void write (byte[] buffer) throws IOException
  {
    out.write(buffer);
  }

  /**
   * This method writes <code>len</code> bytes to the file from the specified
   * array starting at index <code>offset</code> into the array.
   *
   * @param buf The array of bytes to write to the file
   * @param offset The index into the array to start writing file
   * @param len The number of bytes to write
   *
   * @exception IOException If an error occurs
   */
  public void write (byte[] buffer, int offset, int len) throws IOException
  {
    out.write (buffer, offset, len);
  }

  /**
   * This method writes a Java <code>boolean</code> to the underlying output 
   * stream. For a value of <code>true</code>, 1 is written to the stream.
   * For a value of <code>false</code>, 0 is written.
   *
   * @param b The <code>boolean</code> value to write to the stream
   *
   * @exception IOException If an error occurs
   */
  public final void writeBoolean (boolean val) throws IOException
  {
    out.writeBoolean(val);
  }

  /**
   * This method writes a Java <code>byte</code> value to the underlying
   * output stream.
   *
   * @param b The <code>byte</code> to write to the stream, passed 
   * as an <code>int</code>.
   *
   * @exception IOException If an error occurs
   */
  public final void writeByte (int v) throws IOException
  {
    out.writeByte(v);
  }

  /**
   * This method writes a Java <code>short</code> to the stream, high byte
   * first.  This method requires two bytes to encode the value.
   *
   * @param s The <code>short</code> value to write to the stream, 
   * passed as an <code>int</code>.
   *
   * @exception IOException If an error occurs
   */
  public final void writeShort (int v) throws IOException
  {
    out.writeShort(v);
  }

  /**
   * This method writes a single <code>char</code> value to the stream,
   * high byte first.
   *
   * @param v The <code>char</code> value to write, passed as 
   * an <code>int</code>.
   *
   * @exception IOException If an error occurs
   */
  public final void writeChar (int v) throws IOException
  {
    out.writeChar(v);
  }

  /**
   * This method writes a Java <code>int</code> to the stream, high bytes
   * first.  This method requires four bytes to encode the value.
   *
   * @param v The <code>int</code> value to write to the stream.
   *
   * @exception IOException If an error occurs
   */
  public final void writeInt (int v) throws IOException
  {
    out.writeInt(v);
  }

  /**
   * This method writes a Java <code>long</code> to the stream, high bytes
   * first.  This method requires eight bytes to encode the value.
   *
   * @param v The <code>long</code> value to write to the stream.
   *
   * @exception IOException If an error occurs
   */
  public final void writeLong (long v) throws IOException
  {
    out.writeLong(v);
  }

  /**
   * This method writes a Java <code>float</code> value to the stream.  This
   * value is written by first calling the method 
   * <code>Float.floatToIntBits</code>
   * to retrieve an <code>int</code> representing the floating point number,
   * then writing this <code>int</code> value to the stream exactly the same
   * as the <code>writeInt()</code> method does.
   *
   * @param v The floating point number to write to the stream.
   *
   * @exception IOException If an error occurs
   *
   * @see #writeInt(int)
   */
  public final void writeFloat (float v) throws IOException
  {
    out.writeFloat(v);
  }

  /**
   * This method writes a Java <code>double</code> value to the stream.  This
   * value is written by first calling the method 
   * <code>Double.doubleToLongBits</code>
   * to retrieve an <code>long</code> representing the floating point number,
   * then writing this <code>long</code> value to the stream exactly the same
   * as the <code>writeLong()</code> method does.
   *
   * @param v The double precision floating point number to write to the 
   * stream.
   *
   * @exception IOException If an error occurs
   *
   * @see #writeLong(long)
   */
  public final void writeDouble (double v) throws IOException
  {
    out.writeDouble(v);
  }

  /**
   * This method writes all the bytes in a <code>String</code> out to the
   * stream.  One byte is written for each character in the <code>String</code>.
   * The high eight bits of each character are discarded.
   *
   * @param s The <code>String</code> to write to the stream
   *
   * @exception IOException If an error occurs
   */
  public final void writeBytes (String s) throws IOException
  {
    out.writeBytes(s);
  }
  
  /**
   * This method writes all the characters in a <code>String</code> to the
   * stream.  There will be two bytes for each character value.  The high
   * byte of the character will be written first.
   *
   * @param s The <code>String</code> to write to the stream.
   *
   * @exception IOException If an error occurs
   */
  public final void writeChars (String s) throws IOException
  {
    out.writeChars(s);
  }
  
  /**
   * This method writes a Java <code>String</code> to the stream in a modified
   * UTF-8 format.  First, two bytes are written to the stream indicating the
   * number of bytes to follow.  Note that this is the number of bytes in the
   * encoded <code>String</code> not the <code>String</code> length.  Next
   * come the encoded characters.  Each character in the <code>String</code>
   * is encoded as either one, two or three bytes.  For characters in the
   * range of <code>&#92;u0001</code> to <code>&#92;u007F</code>, 
   * one byte is used.  The character
   * value goes into bits 0-7 and bit eight is 0.  For characters in the range
   * of <code>&#92;u0080</code> to <code>&#92;u007FF</code>, two 
   * bytes are used.  Bits
   * 6-10 of the character value are encoded bits 0-4 of the first byte, with
   * the high bytes having a value of "110".  Bits 0-5 of the character value
   * are stored in bits 0-5 of the second byte, with the high bits set to
   * "10".  This type of encoding is also done for the null character
   * <code>&#92;u0000</code>.  This eliminates any C style NUL character values
   * in the output.  All remaining characters are stored as three bytes.
   * Bits 12-15 of the character value are stored in bits 0-3 of the first
   * byte.  The high bits of the first bytes are set to "1110".  Bits 6-11
   * of the character value are stored in bits 0-5 of the second byte.  The
   * high bits of the second byte are set to "10".  And bits 0-5 of the
   * character value are stored in bits 0-5 of byte three, with the high bits
   * of that byte set to "10".
   *
   * @param s The <code>String</code> to write to the output in UTF format
   *
   * @exception IOException If an error occurs
   */
  public final void writeUTF (String s) throws IOException
  {
    out.writeUTF(s);
  }
  
  /**
   * This method creates a java.nio.channels.FileChannel.
   * Nio does not allow one to create a file channel directly.
   * A file channel must be created by first creating an instance of
   * Input/Output/RandomAccessFile and invoking the getChannel() method on it.
   */
  public synchronized FileChannel getChannel ()
  {
    if (ch == null)
      ch = new FileChannelImpl (fd, true, this);

    return ch;
  }

} // class RandomAccessFile

3050'>3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322
/* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
   mapping Object --> Object
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.util;

import gnu.java.lang.CPStringBuilder;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

/**
 * This class provides a red-black tree implementation of the SortedMap
 * interface.  Elements in the Map will be sorted by either a user-provided
 * Comparator object, or by the natural ordering of the keys.
 *
 * The algorithms are adopted from Corman, Leiserson, and Rivest's
 * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
 * insertion and deletion of elements.  That being said, there is a large
 * enough constant coefficient in front of that "log n" (overhead involved
 * in keeping the tree balanced), that TreeMap may not be the best choice
 * for small collections. If something is already sorted, you may want to
 * just use a LinkedHashMap to maintain the order while providing O(1) access.
 *
 * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
 * only if a Comparator is used which can deal with them; natural ordering
 * cannot cope with null.  Null values are always allowed. Note that the
 * ordering must be <i>consistent with equals</i> to correctly implement
 * the Map interface. If this condition is violated, the map is still
 * well-behaved, but you may have suprising results when comparing it to
 * other maps.<p>
 *
 * This implementation is not synchronized. If you need to share this between
 * multiple threads, do something like:<br>
 * <code>SortedMap m
 *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
 *
 * The iterators are <i>fail-fast</i>, meaning that any structural
 * modification, except for <code>remove()</code> called on the iterator
 * itself, cause the iterator to throw a
 * <code>ConcurrentModificationException</code> rather than exhibit
 * non-deterministic behavior.
 *
 * @author Jon Zeppieri
 * @author Bryce McKinlay
 * @author Eric Blake (ebb9@email.byu.edu)
 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
 * @see Map
 * @see HashMap
 * @see Hashtable
 * @see LinkedHashMap
 * @see Comparable
 * @see Comparator
 * @see Collection
 * @see Collections#synchronizedSortedMap(SortedMap)
 * @since 1.2
 * @status updated to 1.6
 */
public class TreeMap<K, V> extends AbstractMap<K, V>
  implements NavigableMap<K, V>, Cloneable, Serializable
{
  // Implementation note:
  // A red-black tree is a binary search tree with the additional properties
  // that all paths to a leaf node visit the same number of black nodes,
  // and no red node has red children. To avoid some null-pointer checks,
  // we use the special node nil which is always black, has no relatives,
  // and has key and value of null (but is not equal to a mapping of null).

  /**
   * Compatible with JDK 1.2.
   */
  private static final long serialVersionUID = 919286545866124006L;

  /**
   * Color status of a node. Package visible for use by nested classes.
   */
  static final int RED = -1,
                   BLACK = 1;

  /**
   * Sentinal node, used to avoid null checks for corner cases and make the
   * delete rebalance code simpler. The rebalance code must never assign
   * the parent, left, or right of nil, but may safely reassign the color
   * to be black. This object must never be used as a key in a TreeMap, or
   * it will break bounds checking of a SubMap.
   */
  static final Node nil = new Node(null, null, BLACK);
  static
    {
      // Nil is self-referential, so we must initialize it after creation.
      nil.parent = nil;
      nil.left = nil;
      nil.right = nil;
    }

  /**
   * The root node of this TreeMap.
   */
  private transient Node root;

  /**
   * The size of this TreeMap. Package visible for use by nested classes.
   */
  transient int size;

  /**
   * The cache for {@link #entrySet()}.
   */
  private transient Set<Map.Entry<K,V>> entries;

  /**
   * The cache for {@link #descendingMap()}.
   */
  private transient NavigableMap<K,V> descendingMap;

  /**
   * The cache for {@link #navigableKeySet()}.
   */
  private transient NavigableSet<K> nKeys;

  /**
   * Counts the number of modifications this TreeMap has undergone, used
   * by Iterators to know when to throw ConcurrentModificationExceptions.
   * Package visible for use by nested classes.
   */
  transient int modCount;

  /**
   * This TreeMap's comparator, or null for natural ordering.
   * Package visible for use by nested classes.
   * @serial the comparator ordering this tree, or null
   */
  final Comparator<? super K> comparator;

  /**
   * Class to represent an entry in the tree. Holds a single key-value pair,
   * plus pointers to parent and child nodes.
   *
   * @author Eric Blake (ebb9@email.byu.edu)
   */
  private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V>
  {
    // All fields package visible for use by nested classes.
    /** The color of this node. */
    int color;

    /** The left child node. */
    Node<K, V> left = nil;
    /** The right child node. */
    Node<K, V> right = nil;
    /** The parent node. */
    Node<K, V> parent = nil;

    /**
     * Simple constructor.
     * @param key the key
     * @param value the value
     */
    Node(K key, V value, int color)
    {
      super(key, value);
      this.color = color;
    }
  }

  /**
   * Instantiate a new TreeMap with no elements, using the keys' natural
   * ordering to sort. All entries in the map must have a key which implements
   * Comparable, and which are <i>mutually comparable</i>, otherwise map
   * operations may throw a {@link ClassCastException}. Attempts to use
   * a null key will throw a {@link NullPointerException}.
   *
   * @see Comparable
   */
  public TreeMap()
  {
    this((Comparator) null);
  }

  /**
   * Instantiate a new TreeMap with no elements, using the provided comparator
   * to sort. All entries in the map must have keys which are mutually
   * comparable by the Comparator, otherwise map operations may throw a
   * {@link ClassCastException}.
   *
   * @param c the sort order for the keys of this map, or null
   *        for the natural order
   */
  public TreeMap(Comparator<? super K> c)
  {
    comparator = c;
    fabricateTree(0);
  }

  /**
   * Instantiate a new TreeMap, initializing it with all of the elements in
   * the provided Map.  The elements will be sorted using the natural
   * ordering of the keys. This algorithm runs in n*log(n) time. All entries
   * in the map must have keys which implement Comparable and are mutually
   * comparable, otherwise map operations may throw a
   * {@link ClassCastException}.
   *
   * @param map a Map, whose entries will be put into this TreeMap
   * @throws ClassCastException if the keys in the provided Map are not
   *         comparable
   * @throws NullPointerException if map is null
   * @see Comparable
   */
  public TreeMap(Map<? extends K, ? extends V> map)
  {
    this((Comparator) null);
    putAll(map);
  }

  /**
   * Instantiate a new TreeMap, initializing it with all of the elements in
   * the provided SortedMap.  The elements will be sorted using the same
   * comparator as in the provided SortedMap. This runs in linear time.
   *
   * @param sm a SortedMap, whose entries will be put into this TreeMap
   * @throws NullPointerException if sm is null
   */
  public TreeMap(SortedMap<K, ? extends V> sm)
  {
    this(sm.comparator());
    int pos = sm.size();
    Iterator itr = sm.entrySet().iterator();

    fabricateTree(pos);
    Node node = firstNode();

    while (--pos >= 0)
      {
        Map.Entry me = (Map.Entry) itr.next();
        node.key = me.getKey();
        node.value = me.getValue();
        node = successor(node);
      }
  }

  /**
   * Clears the Map so it has no keys. This is O(1).
   */
  public void clear()
  {
    if (size > 0)
      {
        modCount++;
        root = nil;
        size = 0;
      }
  }

  /**
   * Returns a shallow clone of this TreeMap. The Map itself is cloned,
   * but its contents are not.
   *
   * @return the clone
   */
  public Object clone()
  {
    TreeMap copy = null;
    try
      {
        copy = (TreeMap) super.clone();
      }
    catch (CloneNotSupportedException x)
      {
      }
    copy.entries = null;
    copy.fabricateTree(size);

    Node node = firstNode();
    Node cnode = copy.firstNode();

    while (node != nil)
      {
        cnode.key = node.key;
        cnode.value = node.value;
        node = successor(node);
        cnode = copy.successor(cnode);
      }
    return copy;
  }

  /**
   * Return the comparator used to sort this map, or null if it is by
   * natural order.
   *
   * @return the map's comparator
   */
  public Comparator<? super K> comparator()
  {
    return comparator;
  }

  /**
   * Returns true if the map contains a mapping for the given key.
   *
   * @param key the key to look for
   * @return true if the key has a mapping
   * @throws ClassCastException if key is not comparable to map elements
   * @throws NullPointerException if key is null and the comparator is not
   *         tolerant of nulls
   */
  public boolean containsKey(Object key)
  {
    return getNode((K) key) != nil;
  }

  /**
   * Returns true if the map contains at least one mapping to the given value.
   * This requires linear time.
   *
   * @param value the value to look for
   * @return true if the value appears in a mapping
   */
  public boolean containsValue(Object value)
  {
    Node node = firstNode();
    while (node != nil)
      {
        if (equals(value, node.value))
          return true;
        node = successor(node);
      }
    return false;
  }

  /**
   * Returns a "set view" of this TreeMap's entries. The set is backed by
   * the TreeMap, so changes in one show up in the other.  The set supports
   * element removal, but not element addition.<p>
   *
   * Note that the iterators for all three views, from keySet(), entrySet(),
   * and values(), traverse the TreeMap in sorted sequence.
   *
   * @return a set view of the entries
   * @see #keySet()
   * @see #values()
   * @see Map.Entry
   */
  public Set<Map.Entry<K,V>> entrySet()
  {
    if (entries == null)
      // Create an AbstractSet with custom implementations of those methods
      // that can be overriden easily and efficiently.
      entries = new NavigableEntrySet();
    return entries;
  }

  /**
   * Returns the first (lowest) key in the map.
   *
   * @return the first key
   * @throws NoSuchElementException if the map is empty
   */
  public K firstKey()
  {
    if (root == nil)
      throw new NoSuchElementException();
    return firstNode().key;
  }

  /**
   * Return the value in this TreeMap associated with the supplied key,
   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
   * could also be null, you must use containsKey to see if this key
   * actually maps to something.
   *
   * @param key the key for which to fetch an associated value
   * @return what the key maps to, if present
   * @throws ClassCastException if key is not comparable to elements in the map
   * @throws NullPointerException if key is null but the comparator does not
   *         tolerate nulls
   * @see #put(Object, Object)
   * @see #containsKey(Object)
   */
  public V get(Object key)
  {
    // Exploit fact that nil.value == null.
    return getNode((K) key).value;
  }

  /**
   * Returns a view of this Map including all entries with keys less than
   * <code>toKey</code>. The returned map is backed by the original, so changes
   * in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoff. The returned map does not include
   * the endpoint; if you want inclusion, pass the successor element
   * or call <code>headMap(toKey, true)</code>.  This is equivalent to
   * calling <code>headMap(toKey, false)</code>.
   *
   * @param toKey the (exclusive) cutoff point
   * @return a view of the map less than the cutoff
   * @throws ClassCastException if <code>toKey</code> is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if toKey is null, but the comparator does not
   *         tolerate null elements
   */
  public SortedMap<K, V> headMap(K toKey)
  {
    return headMap(toKey, false);
  }

  /**
   * Returns a view of this Map including all entries with keys less than
   * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>.
   * The returned map is backed by the original, so changes in one appear
   * in the other. The submap will throw an {@link IllegalArgumentException}
   * for any attempt to access or add an element beyond the specified cutoff. 
   *
   * @param toKey the cutoff point
   * @param inclusive true if the cutoff point should be included.
   * @return a view of the map less than (or equal to, if <code>inclusive</code>
   *         is true) the cutoff.
   * @throws ClassCastException if <code>toKey</code> is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if toKey is null, but the comparator does not
   *         tolerate null elements
   */
  public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
  {
    return new SubMap((K)(Object)nil, inclusive 
		      ? successor(getNode(toKey)).key : toKey);
  }

  /**
   * Returns a "set view" of this TreeMap's keys. The set is backed by the
   * TreeMap, so changes in one show up in the other.  The set supports
   * element removal, but not element addition.
   *
   * @return a set view of the keys
   * @see #values()
   * @see #entrySet()
   */
  public Set<K> keySet()
  {
    if (keys == null)
      // Create an AbstractSet with custom implementations of those methods
      // that can be overriden easily and efficiently.
      keys = new KeySet();
    return keys;
  }

  /**
   * Returns the last (highest) key in the map.
   *
   * @return the last key
   * @throws NoSuchElementException if the map is empty
   */
  public K lastKey()
  {
    if (root == nil)
      throw new NoSuchElementException("empty");
    return lastNode().key;
  }

  /**
   * Puts the supplied value into the Map, mapped by the supplied key.
   * The value may be retrieved by any object which <code>equals()</code>
   * this key. NOTE: Since the prior value could also be null, you must
   * first use containsKey if you want to see if you are replacing the
   * key's mapping.
   *
   * @param key the key used to locate the value
   * @param value the value to be stored in the Map
   * @return the prior mapping of the key, or null if there was none
   * @throws ClassCastException if key is not comparable to current map keys
   * @throws NullPointerException if key is null, but the comparator does
   *         not tolerate nulls
   * @see #get(Object)
   * @see Object#equals(Object)
   */
  public V put(K key, V value)
  {
    Node<K,V> current = root;
    Node<K,V> parent = nil;
    int comparison = 0;

    // Find new node's parent.
    while (current != nil)
      {
        parent = current;
        comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else // Key already in tree.
          return current.setValue(value);
      }

    // Set up new node.
    Node n = new Node(key, value, RED);
    n.parent = parent;

    // Insert node in tree.
    modCount++;
    size++;
    if (parent == nil)
      {
        // Special case inserting into an empty tree.
        root = n;
        return null;
      }
    if (comparison > 0)
      parent.right = n;
    else
      parent.left = n;

    // Rebalance after insert.
    insertFixup(n);
    return null;
  }

  /**
   * Copies all elements of the given map into this TreeMap.  If this map
   * already has a mapping for a key, the new mapping replaces the current
   * one.
   *
   * @param m the map to be added
   * @throws ClassCastException if a key in m is not comparable with keys
   *         in the map
   * @throws NullPointerException if a key in m is null, and the comparator
   *         does not tolerate nulls
   */
  public void putAll(Map<? extends K, ? extends V> m)
  {
    Iterator itr = m.entrySet().iterator();
    int pos = m.size();
    while (--pos >= 0)
      {
        Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
        put(e.getKey(), e.getValue());
      }
  }

  /**
   * Removes from the TreeMap and returns the value which is mapped by the
   * supplied key. If the key maps to nothing, then the TreeMap remains
   * unchanged, and <code>null</code> is returned. NOTE: Since the value
   * could also be null, you must use containsKey to see if you are
   * actually removing a mapping.
   *
   * @param key the key used to locate the value to remove
   * @return whatever the key mapped to, if present
   * @throws ClassCastException if key is not comparable to current map keys
   * @throws NullPointerException if key is null, but the comparator does
   *         not tolerate nulls
   */
  public V remove(Object key)
  {
    Node<K, V> n = getNode((K)key);
    if (n == nil)
      return null;
    // Note: removeNode can alter the contents of n, so save value now.
    V result = n.value;
    removeNode(n);
    return result;
  }

  /**
   * Returns the number of key-value mappings currently in this Map.
   *
   * @return the size
   */
  public int size()
  {
    return size;
  }

  /**
   * Returns a view of this Map including all entries with keys greater or
   * equal to <code>fromKey</code> and less than <code>toKey</code> (a
   * half-open interval). The returned map is backed by the original, so
   * changes in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoffs. The returned map includes the low
   * endpoint but not the high; if you want to reverse this behavior on
   * either end, pass in the successor element or call
   * {@link #subMap(K,boolean,K,boolean)}.  This call is equivalent to
   * <code>subMap(fromKey, true, toKey, false)</code>.
   *
   * @param fromKey the (inclusive) low cutoff point
   * @param toKey the (exclusive) high cutoff point
   * @return a view of the map between the cutoffs
   * @throws ClassCastException if either cutoff is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if fromKey or toKey is null, but the
   *         comparator does not tolerate null elements
   * @throws IllegalArgumentException if fromKey is greater than toKey
   */
  public SortedMap<K, V> subMap(K fromKey, K toKey)
  {
    return subMap(fromKey, true, toKey, false);
  }

  /**
   * Returns a view of this Map including all entries with keys greater (or
   * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and
   * less than (or equal to, if <code>toInclusive</code> is true)
   * <code>toKey</code>. The returned map is backed by the original, so
   * changes in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoffs. 
   *
   * @param fromKey the low cutoff point
   * @param fromInclusive true if the low cutoff point should be included.
   * @param toKey the high cutoff point
   * @param toInclusive true if the high cutoff point should be included.
   * @return a view of the map for the specified range.
   * @throws ClassCastException if either cutoff is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if fromKey or toKey is null, but the
   *         comparator does not tolerate null elements
   * @throws IllegalArgumentException if fromKey is greater than toKey
   */
  public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
				   K toKey, boolean toInclusive)
  {
    return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
		      toInclusive ? successor(getNode(toKey)).key : toKey);
  }

  /**
   * Returns a view of this Map including all entries with keys greater or
   * equal to <code>fromKey</code>. The returned map is backed by the
   * original, so changes in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoff. The returned map includes the
   * endpoint; if you want to exclude it, pass in the successor element.
   * This is equivalent to calling <code>tailMap(fromKey, true)</code>.
   *
   * @param fromKey the (inclusive) low cutoff point
   * @return a view of the map above the cutoff
   * @throws ClassCastException if <code>fromKey</code> is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if fromKey is null, but the comparator
   *         does not tolerate null elements
   */
  public SortedMap<K, V> tailMap(K fromKey)
  {
    return tailMap(fromKey, true);
  }

  /**
   * Returns a view of this Map including all entries with keys greater or
   * equal to <code>fromKey</code>. The returned map is backed by the
   * original, so changes in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoff. The returned map includes the
   * endpoint; if you want to exclude it, pass in the successor element.
   *
   * @param fromKey the low cutoff point
   * @param inclusive true if the cutoff point should be included.
   * @return a view of the map above the cutoff
   * @throws ClassCastException if <code>fromKey</code> is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if fromKey is null, but the comparator
   *         does not tolerate null elements
   */
  public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
  {
    return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
		      (K)(Object)nil);
  }

  /**
   * Returns a "collection view" (or "bag view") of this TreeMap's values.
   * The collection is backed by the TreeMap, so changes in one show up
   * in the other.  The collection supports element removal, but not element
   * addition.
   *
   * @return a bag view of the values
   * @see #keySet()
   * @see #entrySet()
   */
  public Collection<V> values()
  {
    if (values == null)
      // We don't bother overriding many of the optional methods, as doing so
      // wouldn't provide any significant performance advantage.
      values = new AbstractCollection<V>()
      {
        public int size()
        {
          return size;
        }

        public Iterator<V> iterator()
        {
          return new TreeIterator(VALUES);
        }

        public void clear()
        {
          TreeMap.this.clear();
        }
      };
    return values;
  }

  /**
   * Compares two elements by the set comparator, or by natural ordering.
   * Package visible for use by nested classes.
   *
   * @param o1 the first object
   * @param o2 the second object
   * @throws ClassCastException if o1 and o2 are not mutually comparable,
   *         or are not Comparable with natural ordering
   * @throws NullPointerException if o1 or o2 is null with natural ordering
   */
  final int compare(K o1, K o2)
  {
    return (comparator == null
            ? ((Comparable) o1).compareTo(o2)
            : comparator.compare(o1, o2));
  }

  /**
   * Maintain red-black balance after deleting a node.
   *
   * @param node the child of the node just deleted, possibly nil
   * @param parent the parent of the node just deleted, never nil
   */
  private void deleteFixup(Node<K,V> node, Node<K,V> parent)
  {
    // if (parent == nil)
    //   throw new InternalError();
    // If a black node has been removed, we need to rebalance to avoid
    // violating the "same number of black nodes on any path" rule. If
    // node is red, we can simply recolor it black and all is well.
    while (node != root && node.color == BLACK)
      {
        if (node == parent.left)
          {
            // Rebalance left side.
            Node<K,V> sibling = parent.right;
            // if (sibling == nil)
            //   throw new InternalError();
            if (sibling.color == RED)
              {
                // Case 1: Sibling is red.
                // Recolor sibling and parent, and rotate parent left.
                sibling.color = BLACK;
                parent.color = RED;
                rotateLeft(parent);
                sibling = parent.right;
              }

            if (sibling.left.color == BLACK && sibling.right.color == BLACK)
              {
                // Case 2: Sibling has no red children.
                // Recolor sibling, and move to parent.
                sibling.color = RED;
                node = parent;
                parent = parent.parent;
              }
            else
              {
                if (sibling.right.color == BLACK)
                  {
                    // Case 3: Sibling has red left child.
                    // Recolor sibling and left child, rotate sibling right.
                    sibling.left.color = BLACK;
                    sibling.color = RED;
                    rotateRight(sibling);
                    sibling = parent.right;
                  }
                // Case 4: Sibling has red right child. Recolor sibling,
                // right child, and parent, and rotate parent left.
                sibling.color = parent.color;
                parent.color = BLACK;
                sibling.right.color = BLACK;
                rotateLeft(parent);
                node = root; // Finished.
              }
          }
        else
          {
            // Symmetric "mirror" of left-side case.
            Node<K,V> sibling = parent.left;
            // if (sibling == nil)
            //   throw new InternalError();
            if (sibling.color == RED)
              {
                // Case 1: Sibling is red.
                // Recolor sibling and parent, and rotate parent right.
                sibling.color = BLACK;
                parent.color = RED;
                rotateRight(parent);
                sibling = parent.left;
              }

            if (sibling.right.color == BLACK && sibling.left.color == BLACK)
              {
                // Case 2: Sibling has no red children.
                // Recolor sibling, and move to parent.
                sibling.color = RED;
                node = parent;
                parent = parent.parent;
              }
            else
              {
                if (sibling.left.color == BLACK)
                  {
                    // Case 3: Sibling has red right child.
                    // Recolor sibling and right child, rotate sibling left.
                    sibling.right.color = BLACK;
                    sibling.color = RED;
                    rotateLeft(sibling);
                    sibling = parent.left;
                  }
                // Case 4: Sibling has red left child. Recolor sibling,
                // left child, and parent, and rotate parent right.
                sibling.color = parent.color;
                parent.color = BLACK;
                sibling.left.color = BLACK;
                rotateRight(parent);
                node = root; // Finished.
              }
          }
      }
    node.color = BLACK;
  }

  /**
   * Construct a perfectly balanced tree consisting of n "blank" nodes. This
   * permits a tree to be generated from pre-sorted input in linear time.
   *
   * @param count the number of blank nodes, non-negative
   */
  private void fabricateTree(final int count)
  {
    if (count == 0)
      {
	root = nil;
	size = 0;
	return;
      }

    // We color every row of nodes black, except for the overflow nodes.
    // I believe that this is the optimal arrangement. We construct the tree
    // in place by temporarily linking each node to the next node in the row,
    // then updating those links to the children when working on the next row.

    // Make the root node.
    root = new Node(null, null, BLACK);
    size = count;
    Node row = root;
    int rowsize;

    // Fill each row that is completely full of nodes.
    for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
      {
        Node parent = row;
        Node last = null;
        for (int i = 0; i < rowsize; i += 2)
          {
            Node left = new Node(null, null, BLACK);
            Node right = new Node(null, null, BLACK);
            left.parent = parent;
            left.right = right;
            right.parent = parent;
            parent.left = left;
            Node next = parent.right;
            parent.right = right;
            parent = next;
            if (last != null)
              last.right = left;
            last = right;
          }
        row = row.left;
      }

    // Now do the partial final row in red.
    int overflow = count - rowsize;
    Node parent = row;
    int i;
    for (i = 0; i < overflow; i += 2)
      {
        Node left = new Node(null, null, RED);
        Node right = new Node(null, null, RED);
        left.parent = parent;
        right.parent = parent;
        parent.left = left;
        Node next = parent.right;
        parent.right = right;
        parent = next;
      }
    // Add a lone left node if necessary.
    if (i - overflow == 0)
      {
        Node left = new Node(null, null, RED);
        left.parent = parent;
        parent.left = left;
        parent = parent.right;
        left.parent.right = nil;
      }
    // Unlink the remaining nodes of the previous row.
    while (parent != nil)
      {
        Node next = parent.right;
        parent.right = nil;
        parent = next;
      }
  }

  /**
   * Returns the first sorted node in the map, or nil if empty. Package
   * visible for use by nested classes.
   *
   * @return the first node
   */
  final Node<K, V> firstNode()
  {
    // Exploit fact that nil.left == nil.
    Node node = root;
    while (node.left != nil)
      node = node.left;
    return node;
  }

  /**
   * Return the TreeMap.Node associated with key, or the nil node if no such
   * node exists in the tree. Package visible for use by nested classes.
   *
   * @param key the key to search for
   * @return the node where the key is found, or nil
   */
  final Node<K, V> getNode(K key)
  {
    Node<K,V> current = root;
    while (current != nil)
      {
        int comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else
          return current;
      }
    return current;
  }

  /**
   * Find the "highest" node which is &lt; key. If key is nil, return last
   * node. Package visible for use by nested classes.
   *
   * @param key the upper bound, exclusive
   * @return the previous node
   */
  final Node<K,V> highestLessThan(K key)
  {
    return highestLessThan(key, false);
  }

  /**
   * Find the "highest" node which is &lt; (or equal to,
   * if <code>equal</code> is true) key. If key is nil,
   * return last node. Package visible for use by nested
   * classes.
   *
   * @param key the upper bound, exclusive
   * @param equal true if the key should be returned if found.
   * @return the previous node
   */
  final Node<K,V> highestLessThan(K key, boolean equal)
  {
    if (key == nil)
      return lastNode();

    Node<K,V> last = nil;
    Node<K,V> current = root;
    int comparison = 0;

    while (current != nil)
      {
        last = current;
        comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else // Exact match.
          return (equal ? last : predecessor(last));
      }
    return comparison < 0 ? predecessor(last) : last;
  }

  /**
   * Maintain red-black balance after inserting a new node.
   *
   * @param n the newly inserted node
   */
  private void insertFixup(Node<K,V> n)
  {
    // Only need to rebalance when parent is a RED node, and while at least
    // 2 levels deep into the tree (ie: node has a grandparent). Remember
    // that nil.color == BLACK.
    while (n.parent.color == RED && n.parent.parent != nil)
      {
        if (n.parent == n.parent.parent.left)
          {
            Node uncle = n.parent.parent.right;
            // Uncle may be nil, in which case it is BLACK.
            if (uncle.color == RED)
              {
                // Case 1. Uncle is RED: Change colors of parent, uncle,
                // and grandparent, and move n to grandparent.
                n.parent.color = BLACK;
                uncle.color = BLACK;
                uncle.parent.color = RED;
                n = uncle.parent;
              }
            else
              {
                if (n == n.parent.right)
                  {
                    // Case 2. Uncle is BLACK and x is right child.
                    // Move n to parent, and rotate n left.
                    n = n.parent;
                    rotateLeft(n);
                  }
                // Case 3. Uncle is BLACK and x is left child.
                // Recolor parent, grandparent, and rotate grandparent right.
                n.parent.color = BLACK;
                n.parent.parent.color = RED;
                rotateRight(n.parent.parent);
              }
          }
        else
          {
            // Mirror image of above code.
            Node uncle = n.parent.parent.left;
            // Uncle may be nil, in which case it is BLACK.
            if (uncle.color == RED)
              {
                // Case 1. Uncle is RED: Change colors of parent, uncle,
                // and grandparent, and move n to grandparent.
                n.parent.color = BLACK;
                uncle.color = BLACK;
                uncle.parent.color = RED;
                n = uncle.parent;
              }
            else
              {
                if (n == n.parent.left)
                {
                    // Case 2. Uncle is BLACK and x is left child.
                    // Move n to parent, and rotate n right.
                    n = n.parent;
                    rotateRight(n);
                  }
                // Case 3. Uncle is BLACK and x is right child.
                // Recolor parent, grandparent, and rotate grandparent left.
                n.parent.color = BLACK;
                n.parent.parent.color = RED;
                rotateLeft(n.parent.parent);
              }
          }
      }
    root.color = BLACK;
  }

  /**
   * Returns the last sorted node in the map, or nil if empty.
   *
   * @return the last node
   */
  private Node<K,V> lastNode()
  {
    // Exploit fact that nil.right == nil.
    Node node = root;
    while (node.right != nil)
      node = node.right;
    return node;
  }

  /**
   * Find the "lowest" node which is &gt;= key. If key is nil, return either
   * nil or the first node, depending on the parameter first.  Package visible
   * for use by nested classes.
   *
   * @param key the lower bound, inclusive
   * @param first true to return the first element instead of nil for nil key
   * @return the next node
   */
  final Node<K,V> lowestGreaterThan(K key, boolean first)
  {
    return lowestGreaterThan(key, first, true);
  }

  /**
   * Find the "lowest" node which is &gt; (or equal to, if <code>equal</code>
   * is true) key. If key is nil, return either nil or the first node, depending
   * on the parameter first.  Package visible for use by nested classes.
   *
   * @param key the lower bound, inclusive
   * @param first true to return the first element instead of nil for nil key
   * @param equal true if the key should be returned if found.
   * @return the next node
   */
  final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal)
  {
    if (key == nil)
      return first ? firstNode() : nil;

    Node<K,V> last = nil;
    Node<K,V> current = root;
    int comparison = 0;

    while (current != nil)
      {
        last = current;
        comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else
          return (equal ? current : successor(current));
      }
    return comparison > 0 ? successor(last) : last;
  }

  /**
   * Return the node preceding the given one, or nil if there isn't one.
   *
   * @param node the current node, not nil
   * @return the prior node in sorted order
   */
  private Node<K,V> predecessor(Node<K,V> node)
  {
    if (node.left != nil)
      {
        node = node.left;
        while (node.right != nil)
          node = node.right;
        return node;
      }

    Node parent = node.parent;
    // Exploit fact that nil.left == nil and node is non-nil.
    while (node == parent.left)
      {
        node = parent;
        parent = node.parent;
      }
    return parent;
  }

  /**
   * Construct a tree from sorted keys in linear time. Package visible for
   * use by TreeSet.
   *
   * @param s the stream to read from
   * @param count the number of keys to read
   * @param readValues true to read values, false to insert "" as the value
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @see #readObject(ObjectInputStream)
   * @see TreeSet#readObject(ObjectInputStream)
   */
  final void putFromObjStream(ObjectInputStream s, int count,
                              boolean readValues)
    throws IOException, ClassNotFoundException
  {
    fabricateTree(count);
    Node node = firstNode();

    while (--count >= 0)
      {
        node.key = s.readObject();
        node.value = readValues ? s.readObject() : "";
        node = successor(node);
      }
  }

  /**
   * Construct a tree from sorted keys in linear time, with values of "".
   * Package visible for use by TreeSet, which uses a value type of String.
   *
   * @param keys the iterator over the sorted keys
   * @param count the number of nodes to insert
   * @see TreeSet#TreeSet(SortedSet)
   */
  final void putKeysLinear(Iterator<K> keys, int count)
  {
    fabricateTree(count);
    Node<K,V> node = firstNode();

    while (--count >= 0)
      {
        node.key = keys.next();
        node.value = (V) "";
        node = successor(node);
      }
  }

  /**
   * Deserializes this object from the given stream.
   *
   * @param s the stream to read from
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @serialData the <i>size</i> (int), followed by key (Object) and value
   *             (Object) pairs in sorted order
   */
  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    s.defaultReadObject();
    int size = s.readInt();
    putFromObjStream(s, size, true);
  }

  /**
   * Remove node from tree. This will increment modCount and decrement size.
   * Node must exist in the tree. Package visible for use by nested classes.
   *
   * @param node the node to remove
   */
  final void removeNode(Node<K,V> node)
  {
    Node<K,V> splice;
    Node<K,V> child;

    modCount++;
    size--;

    // Find splice, the node at the position to actually remove from the tree.
    if (node.left == nil)
      {
        // Node to be deleted has 0 or 1 children.
        splice = node;
        child = node.right;
      }
    else if (node.right == nil)
      {
        // Node to be deleted has 1 child.
        splice = node;
        child = node.left;
      }
    else
      {
        // Node has 2 children. Splice is node's predecessor, and we swap
        // its contents into node.
        splice = node.left;
        while (splice.right != nil)
          splice = splice.right;
        child = splice.left;
        node.key = splice.key;
        node.value = splice.value;
      }

    // Unlink splice from the tree.
    Node parent = splice.parent;
    if (child != nil)
      child.parent = parent;
    if (parent == nil)
      {
        // Special case for 0 or 1 node remaining.
        root = child;
        return;
      }
    if (splice == parent.left)
      parent.left = child;
    else
      parent.right = child;

    if (splice.color == BLACK)
      deleteFixup(child, parent);
  }

  /**
   * Rotate node n to the left.
   *
   * @param node the node to rotate
   */
  private void rotateLeft(Node<K,V> node)
  {
    Node child = node.right;
    // if (node == nil || child == nil)
    //   throw new InternalError();

    // Establish node.right link.
    node.right = child.left;
    if (child.left != nil)
      child.left.parent = node;

    // Establish child->parent link.
    child.parent = node.parent;
    if (node.parent != nil)
      {
        if (node == node.parent.left)
          node.parent.left = child;
        else
          node.parent.right = child;
      }
    else
      root = child;

    // Link n and child.
    child.left = node;
    node.parent = child;
  }

  /**
   * Rotate node n to the right.
   *
   * @param node the node to rotate
   */
  private void rotateRight(Node<K,V> node)
  {
    Node child = node.left;
    // if (node == nil || child == nil)
    //   throw new InternalError();

    // Establish node.left link.
    node.left = child.right;
    if (child.right != nil)
      child.right.parent = node;

    // Establish child->parent link.
    child.parent = node.parent;
    if (node.parent != nil)
      {
        if (node == node.parent.right)
          node.parent.right = child;
        else
          node.parent.left = child;
      }
    else
      root = child;

    // Link n and child.
    child.right = node;
    node.parent = child;
  }

  /**
   * Return the node following the given one, or nil if there isn't one.
   * Package visible for use by nested classes.
   *
   * @param node the current node, not nil
   * @return the next node in sorted order
   */
  final Node<K,V> successor(Node<K,V> node)
  {
    if (node.right != nil)
      {
        node = node.right;
        while (node.left != nil)
          node = node.left;
        return node;
      }

    Node<K,V> parent = node.parent;
    // Exploit fact that nil.right == nil and node is non-nil.
    while (node == parent.right)
      {
        node = parent;
        parent = parent.parent;
      }
    return parent;
  }

  /**
   * Serializes this object to the given stream.
   *
   * @param s the stream to write to
   * @throws IOException if the underlying stream fails
   * @serialData the <i>size</i> (int), followed by key (Object) and value
   *             (Object) pairs in sorted order
   */
  private void writeObject(ObjectOutputStream s) throws IOException
  {
    s.defaultWriteObject();

    Node node = firstNode();
    s.writeInt(size);
    while (node != nil)
      {
        s.writeObject(node.key);
        s.writeObject(node.value);
        node = successor(node);
      }
  }

  /**
   * Iterate over TreeMap's entries. This implementation is parameterized
   * to give a sequential view of keys, values, or entries.
   *
   * @author Eric Blake (ebb9@email.byu.edu)
   */
  private final class TreeIterator implements Iterator
  {
    /**
     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
     * or {@link #ENTRIES}.
     */
    private final int type;
    /** The number of modifications to the backing Map that we know about. */
    private int knownMod = modCount;
    /** The last Entry returned by a next() call. */
    private Node last;
    /** The next entry that should be returned by next(). */
    private Node next;
    /**
     * The last node visible to this iterator. This is used when iterating
     * on a SubMap.
     */
    private final Node max;

    /**
     * Construct a new TreeIterator with the supplied type.
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     */
    TreeIterator(int type)
    {
      this(type, firstNode(), nil);
    }

    /**
     * Construct a new TreeIterator with the supplied type. Iteration will
     * be from "first" (inclusive) to "max" (exclusive).
     *
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     * @param first where to start iteration, nil for empty iterator
     * @param max the cutoff for iteration, nil for all remaining nodes
     */
    TreeIterator(int type, Node first, Node max)
    {
      this.type = type;
      this.next = first;
      this.max = max;
    }

    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     */
    public boolean hasNext()
    {
      return next != max;
    }

    /**
     * Returns the next element in the Iterator's sequential view.
     * @return the next element
     * @throws ConcurrentModificationException if the TreeMap was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (next == max)
        throw new NoSuchElementException();
      last = next;
      next = successor(last);

      if (type == VALUES)
        return last.value;
      else if (type == KEYS)
        return last.key;
      return last;
    }

    /**
     * Removes from the backing TreeMap the last element which was fetched
     * with the <code>next()</code> method.
     * @throws ConcurrentModificationException if the TreeMap was modified
     * @throws IllegalStateException if called when there is no last element
     */
    public void remove()
    {
      if (last == null)
        throw new IllegalStateException();
      if (knownMod != modCount)
        throw new ConcurrentModificationException();

      removeNode(last);
      last = null;
      knownMod++;
    }
  } // class TreeIterator

  /**
   * Implementation of {@link #subMap(Object, Object)} and other map
   * ranges. This class provides a view of a portion of the original backing
   * map, and throws {@link IllegalArgumentException} for attempts to
   * access beyond that range.
   *
   * @author Eric Blake (ebb9@email.byu.edu)
   */
  private final class SubMap
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>
  {
    /**
     * The lower range of this view, inclusive, or nil for unbounded.
     * Package visible for use by nested classes.
     */
    final K minKey;

    /**
     * The upper range of this view, exclusive, or nil for unbounded.
     * Package visible for use by nested classes.
     */
    final K maxKey;

    /**
     * The cache for {@link #entrySet()}.
     */
    private Set<Map.Entry<K,V>> entries;

    /**
     * The cache for {@link #descendingMap()}.
     */
    private NavigableMap<K,V> descendingMap;

    /**
     * The cache for {@link #navigableKeySet()}.
     */
    private NavigableSet<K> nKeys;

    /**
     * Create a SubMap representing the elements between minKey (inclusive)
     * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
     * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
     *
     * @param minKey the lower bound
     * @param maxKey the upper bound
     * @throws IllegalArgumentException if minKey &gt; maxKey
     */
    SubMap(K minKey, K maxKey)
    {
      if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
        throw new IllegalArgumentException("fromKey > toKey");
      this.minKey = minKey;
      this.maxKey = maxKey;
    }

    /**
     * Check if "key" is in within the range bounds for this SubMap. The
     * lower ("from") SubMap range is inclusive, and the upper ("to") bound
     * is exclusive. Package visible for use by nested classes.
     *
     * @param key the key to check
     * @return true if the key is in range
     */
    boolean keyInRange(K key)
    {
      return ((minKey == nil || compare(key, minKey) >= 0)
              && (maxKey == nil || compare(key, maxKey) < 0));
    }

    public Entry<K,V> ceilingEntry(K key)
    {
      Entry<K,V> n = TreeMap.this.ceilingEntry(key);
      if (n != null && keyInRange(n.getKey()))
	return n;
      return null;
    }

    public K ceilingKey(K key)
    {
      K found = TreeMap.this.ceilingKey(key);
      if (keyInRange(found))
	return found;
      else
	return null;
    }

    public NavigableSet<K> descendingKeySet()
    {
      return descendingMap().navigableKeySet();
    }

    public NavigableMap<K,V> descendingMap()
    {
      if (descendingMap == null)
	descendingMap = new DescendingMap(this);
      return descendingMap;
    }
    
    public void clear()
    {
      Node next = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      while (next != max)
        {
          Node current = next;
          next = successor(current);
          removeNode(current);
        }
    }

    public Comparator<? super K> comparator()
    {
      return comparator;
    }

    public boolean containsKey(Object key)
    {
      return keyInRange((K) key) && TreeMap.this.containsKey(key);
    }

    public boolean containsValue(Object value)
    {
      Node node = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      while (node != max)
        {
          if (equals(value, node.getValue()))
            return true;
          node = successor(node);
        }
      return false;
    }

    public Set<Map.Entry<K,V>> entrySet()
    {
      if (entries == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        entries = new SubMap.NavigableEntrySet();
      return entries;
    }

    public Entry<K,V> firstEntry()
    {
      Node<K,V> node = lowestGreaterThan(minKey, true);
      if (node == nil || ! keyInRange(node.key))
	return null;
      return node;
    }

    public K firstKey()
    {
      Entry<K,V> e = firstEntry();
      if (e == null)
        throw new NoSuchElementException();
      return e.getKey();
    }

    public Entry<K,V> floorEntry(K key)
    {
      Entry<K,V> n = TreeMap.this.floorEntry(key);
      if (n != null && keyInRange(n.getKey()))
	return n;
      return null;
    }

    public K floorKey(K key)
    {
      K found = TreeMap.this.floorKey(key);
      if (keyInRange(found))
	return found;
      else
	return null;
    }

    public V get(Object key)
    {
      if (keyInRange((K) key))
        return TreeMap.this.get(key);
      return null;
    }

    public SortedMap<K,V> headMap(K toKey)
    {
      return headMap(toKey, false);
    }

    public NavigableMap<K,V> headMap(K toKey, boolean inclusive)
    {
      if (!keyInRange(toKey))
        throw new IllegalArgumentException("Key outside submap range");
      return new SubMap(minKey, (inclusive ? 
				 successor(getNode(toKey)).key : toKey));
    }

    public Set<K> keySet()
    {
      if (this.keys == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        this.keys = new SubMap.KeySet();
      return this.keys;
    }

    public Entry<K,V> higherEntry(K key)
    {
      Entry<K,V> n = TreeMap.this.higherEntry(key);
      if (n != null && keyInRange(n.getKey()))
	return n;
      return null;
    }

    public K higherKey(K key)
    {
      K found = TreeMap.this.higherKey(key);
      if (keyInRange(found))
	return found;
      else
	return null;
    }

    public Entry<K,V> lastEntry()
    {
      return lowerEntry(maxKey);
    }

    public K lastKey()
    {
      Entry<K,V> e = lastEntry();
      if (e == null)
        throw new NoSuchElementException();
      return e.getKey();
    }

    public Entry<K,V> lowerEntry(K key)
    {
      Entry<K,V> n = TreeMap.this.lowerEntry(key);
      if (n != null && keyInRange(n.getKey()))
	return n;
      return null;
    }

    public K lowerKey(K key)
    {
      K found = TreeMap.this.lowerKey(key);
      if (keyInRange(found))
	return found;
      else
	return null;
    }

    public NavigableSet<K> navigableKeySet()
    {
      if (this.nKeys == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        this.nKeys = new SubMap.NavigableKeySet();
      return this.nKeys;    
    }

    public Entry<K,V> pollFirstEntry()
    {
      Entry<K,V> e = firstEntry();
      if (e != null)
	removeNode((Node<K,V>) e);
      return e;
    }

    public Entry<K,V> pollLastEntry()
    {
      Entry<K,V> e = lastEntry();
      if (e != null)
	removeNode((Node<K,V>) e);
      return e;
    }

    public V put(K key, V value)
    {
      if (! keyInRange(key))
        throw new IllegalArgumentException("Key outside range");
      return TreeMap.this.put(key, value);
    }

    public V remove(Object key)
    {
      if (keyInRange((K)key))
        return TreeMap.this.remove(key);
      return null;
    }

    public int size()
    {
      Node node = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      int count = 0;
      while (node != max)
        {
          count++;
          node = successor(node);
        }
      return count;
    }

    public SortedMap<K,V> subMap(K fromKey, K toKey)
    {
      return subMap(fromKey, true, toKey, false);
    }

    public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
				    K toKey, boolean toInclusive)
    {
      if (! keyInRange(fromKey) || ! keyInRange(toKey))
        throw new IllegalArgumentException("key outside range");
      return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, 
			toInclusive ? successor(getNode(toKey)).key : toKey);
    }

    public SortedMap<K, V> tailMap(K fromKey)
    {
      return tailMap(fromKey, true);
    }
    
    public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
    {
      if (! keyInRange(fromKey))
        throw new IllegalArgumentException("key outside range");
      return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
			maxKey);
    }

    public Collection<V> values()
    {
      if (this.values == null)
        // Create an AbstractCollection with custom implementations of those
        // methods that can be overriden easily and efficiently.
        this.values = new AbstractCollection()
        {
          public int size()
          {
            return SubMap.this.size();
          }

          public Iterator<V> iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(VALUES, first, max);
          }

          public void clear()
          {
            SubMap.this.clear();
          }
        };
      return this.values;
    }
    
    private class KeySet
      extends AbstractSet<K>
    {
      public int size()
      {
	return SubMap.this.size();
      }
      
      public Iterator<K> iterator()
      {
	Node first = lowestGreaterThan(minKey, true);
	Node max = lowestGreaterThan(maxKey, false);
	return new TreeIterator(KEYS, first, max);
      }
      
      public void clear()
      {
	SubMap.this.clear();
      }
      
      public boolean contains(Object o)
      {
	if (! keyInRange((K) o))
	  return false;
	return getNode((K) o) != nil;
      }
      
      public boolean remove(Object o)
      {
	if (! keyInRange((K) o))
	  return false;
	Node n = getNode((K) o);
	if (n != nil)
	  {
	    removeNode(n);
	    return true;
	  }
	return false;
      }
      
    } // class SubMap.KeySet

    private final class NavigableKeySet
      extends KeySet
      implements NavigableSet<K>
    {

      public K ceiling(K k)
      {
	return SubMap.this.ceilingKey(k);
      }
      
      public Comparator<? super K> comparator()
      {
	return comparator;
      }
      
      public Iterator<K> descendingIterator()
      {
	return descendingSet().iterator();
      }
      
      public NavigableSet<K> descendingSet()
      {
	return new DescendingSet(this);
      }
      
      public K first()
      {
	return SubMap.this.firstKey();
      }
      
      public K floor(K k)
      {
	return SubMap.this.floorKey(k);
      }
      
      public SortedSet<K> headSet(K to)
      {
	return headSet(to, false);
      }

      public NavigableSet<K> headSet(K to, boolean inclusive)
      {
	return SubMap.this.headMap(to, inclusive).navigableKeySet();
      }

      public K higher(K k)
      {
	return SubMap.this.higherKey(k);
      }

      public K last()
      {
	return SubMap.this.lastKey();
      }

      public K lower(K k)
      {
	return SubMap.this.lowerKey(k);
      }

      public K pollFirst()
      {
	return SubMap.this.pollFirstEntry().getKey();
      }

      public K pollLast()
      {
	return SubMap.this.pollLastEntry().getKey();
      }

      public SortedSet<K> subSet(K from, K to)
      {
	return subSet(from, true, to, false);
      }
      
      public NavigableSet<K> subSet(K from, boolean fromInclusive,
				    K to, boolean toInclusive)
      {
	return SubMap.this.subMap(from, fromInclusive,
				  to, toInclusive).navigableKeySet();
      }

      public SortedSet<K> tailSet(K from)
      {
	return tailSet(from, true);
      }
      
      public NavigableSet<K> tailSet(K from, boolean inclusive)
      {
	return SubMap.this.tailMap(from, inclusive).navigableKeySet();
      }
      
  } // class SubMap.NavigableKeySet

  /**
   * Implementation of {@link #entrySet()}.
   */
  private class EntrySet
    extends AbstractSet<Entry<K,V>>
  {
    
    public int size()
    {
      return SubMap.this.size();
    }
    
    public Iterator<Map.Entry<K,V>> iterator()
    {
      Node first = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      return new TreeIterator(ENTRIES, first, max);
    }
    
    public void clear()
    {
      SubMap.this.clear();
    }
    
    public boolean contains(Object o)
    {
      if (! (o instanceof Map.Entry))
	return false;
      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
      K key = me.getKey();
      if (! keyInRange(key))
	return false;
      Node<K,V> n = getNode(key);
      return n != nil && AbstractSet.equals(me.getValue(), n.value);
    }
    
    public boolean remove(Object o)
    {
      if (! (o instanceof Map.Entry))
	return false;
      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
      K key = me.getKey();
      if (! keyInRange(key))
	return false;
      Node<K,V> n = getNode(key);
      if (n != nil && AbstractSet.equals(me.getValue(), n.value))
	{
	  removeNode(n);
	  return true;
	}
      return false;
    }
  } // class SubMap.EntrySet
    
    private final class NavigableEntrySet
      extends EntrySet
      implements NavigableSet<Entry<K,V>>
    {

      public Entry<K,V> ceiling(Entry<K,V> e)
      {
	return SubMap.this.ceilingEntry(e.getKey());
      }
      
      public Comparator<? super Entry<K,V>> comparator()
      {
	return new Comparator<Entry<K,V>>()
	  {
	    public int compare(Entry<K,V> t1, Entry<K,V> t2)
	      {
		return comparator.compare(t1.getKey(), t2.getKey());
	      }
	  };
      }
      
      public Iterator<Entry<K,V>> descendingIterator()
      {
	return descendingSet().iterator();
      }
      
      public NavigableSet<Entry<K,V>> descendingSet()
      {
	return new DescendingSet(this);
      }
      
      public Entry<K,V> first()
      {
	return SubMap.this.firstEntry();
      }
      
      public Entry<K,V> floor(Entry<K,V> e)
      {
	return SubMap.this.floorEntry(e.getKey());
      }
      
      public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
      {
	return headSet(to, false);
      }

      public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
      {
	return (NavigableSet<Entry<K,V>>)
	  SubMap.this.headMap(to.getKey(), inclusive).entrySet();
      }

      public Entry<K,V> higher(Entry<K,V> e)
      {
	return SubMap.this.higherEntry(e.getKey());
      }

      public Entry<K,V> last()
      {
	return SubMap.this.lastEntry();
      }

      public Entry<K,V> lower(Entry<K,V> e)
      {
	return SubMap.this.lowerEntry(e.getKey());
      }

      public Entry<K,V> pollFirst()
      {
	return SubMap.this.pollFirstEntry();
      }

      public Entry<K,V> pollLast()
      {
	return SubMap.this.pollLastEntry();
      }

      public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
      {
	return subSet(from, true, to, false);
      }
      
      public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
					     Entry<K,V> to, boolean toInclusive)
      {
	return (NavigableSet<Entry<K,V>>)
	  SubMap.this.subMap(from.getKey(), fromInclusive,
			     to.getKey(), toInclusive).entrySet();
      }

      public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
      {
	return tailSet(from, true);
      }
      
      public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
      {
	return (NavigableSet<Entry<K,V>>)
	  SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet();
      }
      
  } // class SubMap.NavigableEntrySet

} // class SubMap  

  /**
   * Returns the entry associated with the least or lowest key
   * that is greater than or equal to the specified key, or
   * <code>null</code> if there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the entry with the least key greater than or equal
   *         to the given key, or <code>null</code> if there is
   *         no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public Entry<K,V> ceilingEntry(K key)
  {
    Node<K,V> n = lowestGreaterThan(key, false);
    return (n == nil) ? null : n;
  }

  /**
   * Returns the the least or lowest key that is greater than
   * or equal to the specified key, or <code>null</code> if
   * there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the least key greater than or equal to the given key,
   *         or <code>null</code> if there is no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public K ceilingKey(K key)
  {
    Entry<K,V> e = ceilingEntry(key);
    return (e == null) ? null : e.getKey();
  }

  /**
   * Returns a reverse ordered {@link NavigableSet} view of this
   * map's keys. The set is backed by the {@link TreeMap}, so changes
   * in one show up in the other.  The set supports element removal,
   * but not element addition.
   *
   * @return a reverse ordered set view of the keys.
   * @since 1.6
   * @see #descendingMap()
   */
  public NavigableSet<K> descendingKeySet()
  {
    return descendingMap().navigableKeySet();
  }

  /**
   * Returns a view of the map in reverse order.  The descending map
   * is backed by the original map, so that changes affect both maps.
   * Any changes occurring to either map while an iteration is taking
   * place (with the exception of a {@link Iterator#remove()} operation)
   * result in undefined behaviour from the iteration.  The ordering
   * of the descending map is the same as for a map with a
   * {@link Comparator} given by {@link Collections#reverseOrder()},
   * and calling {@link #descendingMap()} on the descending map itself
   * results in a view equivalent to the original map.
   *
   * @return a reverse order view of the map.
   * @since 1.6
   */
  public NavigableMap<K,V> descendingMap()
  {
    if (descendingMap == null)
      descendingMap = new DescendingMap<K,V>(this);
    return descendingMap;
  }

  /**
   * Returns the entry associated with the least or lowest key
   * in the map, or <code>null</code> if the map is empty.
   *
   * @return the lowest entry, or <code>null</code> if the map
   *         is empty.
   * @since 1.6
   */
  public Entry<K,V> firstEntry()
  {
    Node<K,V> n = firstNode();
    return (n == nil) ? null : n;
  }

  /**
   * Returns the entry associated with the greatest or highest key
   * that is less than or equal to the specified key, or
   * <code>null</code> if there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the entry with the greatest key less than or equal
   *         to the given key, or <code>null</code> if there is
   *         no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public Entry<K,V> floorEntry(K key)
  {
    Node<K,V> n = highestLessThan(key, true);
    return (n == nil) ? null : n;
  }

  /**
   * Returns the the greatest or highest key that is less than
   * or equal to the specified key, or <code>null</code> if
   * there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the greatest key less than or equal to the given key,
   *         or <code>null</code> if there is no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public K floorKey(K key)
  {
    Entry<K,V> e = floorEntry(key);
    return (e == null) ? null : e.getKey();
  }

  /**
   * Returns the entry associated with the least or lowest key
   * that is strictly greater than the specified key, or
   * <code>null</code> if there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the entry with the least key greater than 
   *         the given key, or <code>null</code> if there is
   *         no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public Entry<K,V> higherEntry(K key)
  {
    Node<K,V> n = lowestGreaterThan(key, false, false);
    return (n == nil) ? null : n;
  }

  /**
   * Returns the the least or lowest key that is strictly
   * greater than the specified key, or <code>null</code> if
   * there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the least key greater than the given key,
   *         or <code>null</code> if there is no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public K higherKey(K key)
  {
    Entry<K,V> e = higherEntry(key);
    return (e == null) ? null : e.getKey();
  }

  /**
   * Returns the entry associated with the greatest or highest key
   * in the map, or <code>null</code> if the map is empty.
   *
   * @return the highest entry, or <code>null</code> if the map
   *         is empty.
   * @since 1.6
   */
  public Entry<K,V> lastEntry()
  {
    Node<K,V> n = lastNode();
    return (n == nil) ? null : n;
  }

  /**
   * Returns the entry associated with the greatest or highest key
   * that is strictly less than the specified key, or
   * <code>null</code> if there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the entry with the greatest key less than 
   *         the given key, or <code>null</code> if there is
   *         no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public Entry<K,V> lowerEntry(K key)
  {
    Node<K,V> n = highestLessThan(key);
    return (n == nil) ? null : n;
  }

  /**
   * Returns the the greatest or highest key that is strictly
   * less than the specified key, or <code>null</code> if
   * there is no such key.
   *
   * @param key the key relative to the returned entry.
   * @return the greatest key less than the given key,
   *         or <code>null</code> if there is no such key.
   * @throws ClassCastException if the specified key can not
   *                            be compared with those in the map.
   * @throws NullPointerException if the key is <code>null</code>
   *                              and this map either uses natural
   *                              ordering or a comparator that does
   *                              not permit null keys.
   * @since 1.6
   */
  public K lowerKey(K key)
  {
    Entry<K,V> e = lowerEntry(key);
    return (e == null) ? null : e.getKey();
  }

  /**
   * Returns a {@link NavigableSet} view of this map's keys. The set is
   * backed by the {@link TreeMap}, so changes in one show up in the other.
   * Any changes occurring to either while an iteration is taking
   * place (with the exception of a {@link Iterator#remove()} operation)
   * result in undefined behaviour from the iteration.  The ordering
   * The set supports element removal, but not element addition.
   *
   * @return a {@link NavigableSet} view of the keys.
   * @since 1.6
   */
  public NavigableSet<K> navigableKeySet()
  {
    if (nKeys == null)
      nKeys = new NavigableKeySet();
    return nKeys;
  }

  /**
   * Removes and returns the entry associated with the least
   * or lowest key in the map, or <code>null</code> if the map
   * is empty.
   *
   * @return the removed first entry, or <code>null</code> if the
   *         map is empty.
   * @since 1.6
   */
  public Entry<K,V> pollFirstEntry()
  {
    Entry<K,V> e = firstEntry();
    if (e != null)
      removeNode((Node<K,V>)e);
    return e;
  }

  /**
   * Removes and returns the entry associated with the greatest
   * or highest key in the map, or <code>null</code> if the map
   * is empty.
   *
   * @return the removed last entry, or <code>null</code> if the
   *         map is empty.
   * @since 1.6
   */
  public Entry<K,V> pollLastEntry()
  {
    Entry<K,V> e = lastEntry();
    if (e != null)
      removeNode((Node<K,V>)e);
    return e;    
  }

  /**
   * Implementation of {@link #descendingMap()} and associated
   * derivatives. This class provides a view of the
   * original backing map in reverse order, and throws
   * {@link IllegalArgumentException} for attempts to
   * access beyond that range.
   *
   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
   */
  private static final class DescendingMap<DK,DV>
    implements NavigableMap<DK,DV>
  {

    /**
     * The cache for {@link #entrySet()}.
     */
    private Set<Map.Entry<DK,DV>> entries;

    /**
     * The cache for {@link #keySet()}.
     */
    private Set<DK> keys;

    /**
     * The cache for {@link #navigableKeySet()}.
     */
    private NavigableSet<DK> nKeys;

    /**
     * The cache for {@link #values()}.
     */
    private Collection<DV> values;

    /**
     * The backing {@link NavigableMap}.
     */
    private NavigableMap<DK,DV> map;

    /**
     * Create a {@link DescendingMap} around the specified
     * map.
     *
     * @param map the map to wrap.
     */
    public DescendingMap(NavigableMap<DK,DV> map)
    {
      this.map = map;
    }
      
    public Map.Entry<DK,DV> ceilingEntry(DK key)
    {
      return map.floorEntry(key);
    }

    public DK ceilingKey(DK key)
    {
      return map.floorKey(key);
    }

    public void clear()
    {
      map.clear();
    }

    public Comparator<? super DK> comparator()
    {
      return Collections.reverseOrder(map.comparator());
    }

    public boolean containsKey(Object o)
    {
      return map.containsKey(o);
    }
    
    public boolean containsValue(Object o)
    {
      return map.containsValue(o);
    }

    public NavigableSet<DK> descendingKeySet()
    {
      return descendingMap().navigableKeySet();
    }

    public NavigableMap<DK,DV> descendingMap()
    {
      return map;
    }

    public Set<Entry<DK,DV>> entrySet()
    {
      if (entries == null)
	entries =
	  new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>)
					  map.entrySet());
      return entries;
    }

    public boolean equals(Object o)
    {
      return map.equals(o);
    }

    public Entry<DK,DV> firstEntry()
    {
      return map.lastEntry();
    }

    public DK firstKey()
    {
      return map.lastKey();
    }

    public Entry<DK,DV> floorEntry(DK key)
    {
      return map.ceilingEntry(key);
    }

    public DK floorKey(DK key)
    {
      return map.ceilingKey(key);
    }

    public DV get(Object key)
    {
      return map.get(key);
    }

    public int hashCode()
    {
      return map.hashCode();
    }

    public SortedMap<DK,DV> headMap(DK toKey)
    {
      return headMap(toKey, false);
    }

    public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive)
    {
      return new DescendingMap(map.tailMap(toKey, inclusive));
    }

    public Entry<DK,DV> higherEntry(DK key)
    {
      return map.lowerEntry(key);
    }

    public DK higherKey(DK key)
    {
      return map.lowerKey(key);
    }

    public Set<DK> keySet()
    {
      if (keys == null)
	keys = new DescendingSet<DK>(map.navigableKeySet());
      return keys;
    }

    public boolean isEmpty()
    {
      return map.isEmpty();
    }

    public Entry<DK,DV> lastEntry()
    {
      return map.firstEntry();
    }

    public DK lastKey()
    {
      return map.firstKey();
    }

    public Entry<DK,DV> lowerEntry(DK key)
    {
      return map.higherEntry(key);
    }

    public DK lowerKey(DK key)
    {
      return map.higherKey(key);
    }

    public NavigableSet<DK> navigableKeySet()
    {
      if (nKeys == null)
	nKeys = new DescendingSet<DK>(map.navigableKeySet());
      return nKeys;
    }

    public Entry<DK,DV> pollFirstEntry()
    {
      return pollLastEntry();
    }

    public Entry<DK,DV> pollLastEntry()
    {
      return pollFirstEntry();
    }

    public DV put(DK key, DV value)
    {
      return map.put(key, value);
    }

    public void putAll(Map<? extends DK, ? extends DV> m)
    {
      map.putAll(m);
    }

    public DV remove(Object key)
    {
      return map.remove(key);
    }

    public int size()
    {
      return map.size();
    }

    public SortedMap<DK,DV> subMap(DK fromKey, DK toKey)
    {
      return subMap(fromKey, true, toKey, false);
    }

    public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive,
				      DK toKey, boolean toInclusive)
    {
      return new DescendingMap(map.subMap(fromKey, fromInclusive,
					  toKey, toInclusive));
    }

    public SortedMap<DK,DV> tailMap(DK fromKey)
    {
      return tailMap(fromKey, true);
    }

    public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive)
    {
      return new DescendingMap(map.headMap(fromKey, inclusive));
    }

    public String toString()
    {
      CPStringBuilder r = new CPStringBuilder("{");
      final Iterator<Entry<DK,DV>> it = entrySet().iterator();
      while (it.hasNext())
      {
	final Entry<DK,DV> e = it.next();
        r.append(e.getKey());
        r.append('=');
        r.append(e.getValue());
	r.append(", ");
      }
      r.replace(r.length() - 2, r.length(), "}");
      return r.toString();
    }

    public Collection<DV> values()
    {
      if (values == null)
        // Create an AbstractCollection with custom implementations of those
        // methods that can be overriden easily and efficiently.
        values = new AbstractCollection()
	  {
	    public int size()
	    {
	      return DescendingMap.this.size();
	    }
	    
	    public Iterator<DV> iterator()
	    {
	      return new Iterator<DV>()
		{	  
		  /** The last Entry returned by a next() call. */
		  private Entry<DK,DV> last;
		  
		  /** The next entry that should be returned by next(). */
		  private Entry<DK,DV> next = firstEntry();
		  
		  public boolean hasNext()
		  {
		    return next != null;
		  }

		  public DV next()
		  {
		    if (next == null)
		      throw new NoSuchElementException();
		    last = next;
		    next = higherEntry(last.getKey());
		    
		    return last.getValue();
		  }

		  public void remove()
		  {
		    if (last == null)
		      throw new IllegalStateException();
		    
		    DescendingMap.this.remove(last.getKey());
		    last = null;
		  }
		};
	    }
	    
	    public void clear()
	    {
	      DescendingMap.this.clear();
	    }
	  };
      return values;
    }

  } // class DescendingMap

  /**
   * Implementation of {@link #keySet()}.
   */
  private class KeySet
    extends AbstractSet<K>
  {

    public int size()
    {
      return size;
    }

    public Iterator<K> iterator()
    {
      return new TreeIterator(KEYS);
    }

    public void clear()
    {
      TreeMap.this.clear();
    }
    
    public boolean contains(Object o)
    {
      return containsKey(o);
    }
    
    public boolean remove(Object key)
    {
      Node<K,V> n = getNode((K) key);
      if (n == nil)
	return false;
      removeNode(n);