001/* TreeSet.java -- a class providing a TreeMap-backed SortedSet 002 Copyright (C) 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 003 004This file is part of GNU Classpath. 005 006GNU Classpath is free software; you can redistribute it and/or modify 007it under the terms of the GNU General Public License as published by 008the Free Software Foundation; either version 2, or (at your option) 009any later version. 010 011GNU Classpath is distributed in the hope that it will be useful, but 012WITHOUT ANY WARRANTY; without even the implied warranty of 013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014General Public License for more details. 015 016You should have received a copy of the GNU General Public License 017along with GNU Classpath; see the file COPYING. If not, write to the 018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 01902110-1301 USA. 020 021Linking this library statically or dynamically with other modules is 022making a combined work based on this library. Thus, the terms and 023conditions of the GNU General Public License cover the whole 024combination. 025 026As a special exception, the copyright holders of this library give you 027permission to link this library with independent modules to produce an 028executable, regardless of the license terms of these independent 029modules, and to copy and distribute the resulting executable under 030terms of your choice, provided that you also meet, for each linked 031independent module, the terms and conditions of the license of that 032module. An independent module is a module which is not derived from 033or based on this library. If you modify this library, you may extend 034this exception to your version of the library, but you are not 035obligated to do so. If you do not wish to do so, delete this 036exception statement from your version. */ 037 038 039package java.util; 040 041import java.io.IOException; 042import java.io.ObjectInputStream; 043import java.io.ObjectOutputStream; 044import java.io.Serializable; 045 046/** 047 * This class provides a TreeMap-backed implementation of the SortedSet 048 * interface. The elements will be sorted according to their <i>natural 049 * order</i>, or according to the provided <code>Comparator</code>.<p> 050 * 051 * Most operations are O(log n), but there is so much overhead that this 052 * makes small sets expensive. Note that the ordering must be <i>consistent 053 * with equals</i> to correctly implement the Set interface. If this 054 * condition is violated, the set is still well-behaved, but you may have 055 * suprising results when comparing it to other sets.<p> 056 * 057 * This implementation is not synchronized. If you need to share this between 058 * multiple threads, do something like:<br> 059 * <code>SortedSet s 060 * = Collections.synchronizedSortedSet(new TreeSet(...));</code><p> 061 * 062 * The iterators are <i>fail-fast</i>, meaning that any structural 063 * modification, except for <code>remove()</code> called on the iterator 064 * itself, cause the iterator to throw a 065 * <code>ConcurrentModificationException</code> rather than exhibit 066 * non-deterministic behavior. 067 * 068 * @author Jon Zeppieri 069 * @author Bryce McKinlay 070 * @author Eric Blake (ebb9@email.byu.edu) 071 * @author Tom Tromey (tromey@redhat.com) 072 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 073 * @see Collection 074 * @see Set 075 * @see HashSet 076 * @see LinkedHashSet 077 * @see Comparable 078 * @see Comparator 079 * @see Collections#synchronizedSortedSet(SortedSet) 080 * @see TreeMap 081 * @since 1.2 082 * @status updated to 1.6 083 */ 084public class TreeSet<T> extends AbstractSet<T> 085 implements NavigableSet<T>, Cloneable, Serializable 086{ 087 /** 088 * Compatible with JDK 1.2. 089 */ 090 private static final long serialVersionUID = -2479143000061671589L; 091 092 /** 093 * The NavigableMap which backs this Set. 094 */ 095 // Not final because of readObject. This will always be one of TreeMap or 096 // TreeMap.SubMap, which both extend AbstractMap. 097 private transient NavigableMap<T, String> map; 098 099 /** 100 * Construct a new TreeSet whose backing TreeMap using the "natural" 101 * ordering of keys. Elements that are not mutually comparable will cause 102 * ClassCastExceptions down the road. 103 * 104 * @see Comparable 105 */ 106 public TreeSet() 107 { 108 map = new TreeMap<T, String>(); 109 } 110 111 /** 112 * Construct a new TreeSet whose backing TreeMap uses the supplied 113 * Comparator. Elements that are not mutually comparable will cause 114 * ClassCastExceptions down the road. 115 * 116 * @param comparator the Comparator this Set will use 117 */ 118 public TreeSet(Comparator<? super T> comparator) 119 { 120 map = new TreeMap<T, String>(comparator); 121 } 122 123 /** 124 * Construct a new TreeSet whose backing TreeMap uses the "natural" 125 * orering of the keys and which contains all of the elements in the 126 * supplied Collection. This runs in n*log(n) time. 127 * 128 * @param collection the new Set will be initialized with all 129 * of the elements in this Collection 130 * @throws ClassCastException if the elements of the collection are not 131 * comparable 132 * @throws NullPointerException if the collection is null 133 * @see Comparable 134 */ 135 public TreeSet(Collection<? extends T> collection) 136 { 137 map = new TreeMap<T, String>(); 138 addAll(collection); 139 } 140 141 /** 142 * Construct a new TreeSet, using the same key ordering as the supplied 143 * SortedSet and containing all of the elements in the supplied SortedSet. 144 * This constructor runs in linear time. 145 * 146 * @param sortedSet the new TreeSet will use this SortedSet's comparator 147 * and will initialize itself with all its elements 148 * @throws NullPointerException if sortedSet is null 149 */ 150 public TreeSet(SortedSet<T> sortedSet) 151 { 152 Iterator<T> itr; 153 154 map = new TreeMap<T, String> 155 ((Comparator<? super T>)sortedSet.comparator()); 156 itr = ((SortedSet<T>) sortedSet).iterator(); 157 ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size()); 158 } 159 160 /** 161 * This private constructor is used to implement the subSet() calls around 162 * a backing TreeMap.SubMap. 163 * 164 * @param backingMap the submap 165 */ 166 private TreeSet(NavigableMap<T,String> backingMap) 167 { 168 map = backingMap; 169 } 170 171 /** 172 * Adds the spplied Object to the Set if it is not already in the Set; 173 * returns true if the element is added, false otherwise. 174 * 175 * @param obj the Object to be added to this Set 176 * @throws ClassCastException if the element cannot be compared with objects 177 * already in the set 178 */ 179 public boolean add(T obj) 180 { 181 return map.put(obj, "") == null; 182 } 183 184 /** 185 * Adds all of the elements in the supplied Collection to this TreeSet. 186 * 187 * @param c The collection to add 188 * @return true if the Set is altered, false otherwise 189 * @throws NullPointerException if c is null 190 * @throws ClassCastException if an element in c cannot be compared with 191 * objects already in the set 192 */ 193 public boolean addAll(Collection<? extends T> c) 194 { 195 boolean result = false; 196 int pos = c.size(); 197 Iterator<? extends T> itr = c.iterator(); 198 while (--pos >= 0) 199 result |= (map.put(itr.next(), "") == null); 200 return result; 201 } 202 203 /** 204 * Removes all elements in this Set. 205 */ 206 public void clear() 207 { 208 map.clear(); 209 } 210 211 /** 212 * Returns a shallow copy of this Set. The elements are not cloned. 213 * 214 * @return the cloned set 215 */ 216 public Object clone() 217 { 218 TreeSet<T> copy = null; 219 try 220 { 221 copy = (TreeSet<T>) super.clone(); 222 // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts. 223 copy.map = (NavigableMap<T, String>) ((AbstractMap<T, String>) map).clone(); 224 } 225 catch (CloneNotSupportedException x) 226 { 227 // Impossible result. 228 } 229 return copy; 230 } 231 232 /** 233 * Returns this Set's comparator. 234 * 235 * @return the comparator, or null if the set uses natural ordering 236 */ 237 public Comparator<? super T> comparator() 238 { 239 return map.comparator(); 240 } 241 242 /** 243 * Returns true if this Set contains the supplied Object, false otherwise. 244 * 245 * @param obj the Object to check for 246 * @return true if it is in the set 247 * @throws ClassCastException if obj cannot be compared with objects 248 * already in the set 249 */ 250 public boolean contains(Object obj) 251 { 252 return map.containsKey(obj); 253 } 254 255 /** 256 * Returns the first (by order) element in this Set. 257 * 258 * @return the first element 259 * @throws NoSuchElementException if the set is empty 260 */ 261 public T first() 262 { 263 return map.firstKey(); 264 } 265 266 /** 267 * Returns a view of this Set including all elements less than 268 * <code>to</code>. The returned set is backed by the original, so changes 269 * in one appear in the other. The subset will throw an 270 * {@link IllegalArgumentException} for any attempt to access or add an 271 * element beyond the specified cutoff. The returned set does not include 272 * the endpoint; if you want inclusion, pass the successor element or 273 * call {@link #headSet(T,boolean)}. This call is equivalent to 274 * <code>headSet(to, false)</code>. 275 * 276 * @param to the (exclusive) cutoff point 277 * @return a view of the set less than the cutoff 278 * @throws ClassCastException if <code>to</code> is not compatible with 279 * the comparator (or is not Comparable, for natural ordering) 280 * @throws NullPointerException if to is null, but the comparator does not 281 * tolerate null elements 282 */ 283 public SortedSet<T> headSet(T to) 284 { 285 return headSet(to, false); 286 } 287 288 /** 289 * Returns a view of this Set including all elements less than 290 * (or equal to, if <code>inclusive</code> is true) <code>to</code>. 291 * The returned set is backed by the original, so changes 292 * in one appear in the other. The subset will throw an 293 * {@link IllegalArgumentException} for any attempt to access or add an 294 * element beyond the specified cutoff. 295 * 296 * @param to the cutoff point 297 * @param inclusive true if <code>to</code> should be included. 298 * @return a view of the set for the specified range. 299 * @throws ClassCastException if <code>to</code> is not compatible with 300 * the comparator (or is not Comparable, for natural ordering) 301 * @throws NullPointerException if to is null, but the comparator does not 302 * tolerate null elements 303 */ 304 public NavigableSet<T> headSet(T to, boolean inclusive) 305 { 306 return new TreeSet<T>(map.headMap(to, inclusive)); 307 } 308 309 /** 310 * Returns true if this Set has size 0, false otherwise. 311 * 312 * @return true if the set is empty 313 */ 314 public boolean isEmpty() 315 { 316 return map.isEmpty(); 317 } 318 319 /** 320 * Returns in Iterator over the elements in this TreeSet, which traverses 321 * in ascending order. 322 * 323 * @return an iterator 324 */ 325 public Iterator<T> iterator() 326 { 327 return map.keySet().iterator(); 328 } 329 330 /** 331 * Returns the last (by order) element in this Set. 332 * 333 * @return the last element 334 * @throws NoSuchElementException if the set is empty 335 */ 336 public T last() 337 { 338 return map.lastKey(); 339 } 340 341 /** 342 * If the supplied Object is in this Set, it is removed, and true is 343 * returned; otherwise, false is returned. 344 * 345 * @param obj the Object to remove from this Set 346 * @return true if the set was modified 347 * @throws ClassCastException if obj cannot be compared to set elements 348 */ 349 public boolean remove(Object obj) 350 { 351 return map.remove(obj) != null; 352 } 353 354 /** 355 * Returns the number of elements in this Set 356 * 357 * @return the set size 358 */ 359 public int size() 360 { 361 return map.size(); 362 } 363 364 /** 365 * Returns a view of this Set including all elements greater or equal to 366 * <code>from</code> and less than <code>to</code> (a half-open interval). 367 * The returned set is backed by the original, so changes in one appear in 368 * the other. The subset will throw an {@link IllegalArgumentException} 369 * for any attempt to access or add an element beyond the specified cutoffs. 370 * The returned set includes the low endpoint but not the high; if you want 371 * to reverse this behavior on either end, pass in the successor element 372 * or call {@link #subSet(T,boolean,T,boolean)}. This is equivalent to 373 * calling <code>subSet(from,true,to,false)</code>. 374 * 375 * @param from the (inclusive) low cutoff point 376 * @param to the (exclusive) high cutoff point 377 * @return a view of the set between the cutoffs 378 * @throws ClassCastException if either cutoff is not compatible with 379 * the comparator (or is not Comparable, for natural ordering) 380 * @throws NullPointerException if from or to is null, but the comparator 381 * does not tolerate null elements 382 * @throws IllegalArgumentException if from is greater than to 383 */ 384 public SortedSet<T> subSet(T from, T to) 385 { 386 return subSet(from, true, to, false); 387 } 388 389 /** 390 * Returns a view of this Set including all elements greater than (or equal to, 391 * if <code>fromInclusive</code> is true</code> <code>from</code> and less than 392 * (or equal to, if <code>toInclusive</code> is true) <code>to</code>. 393 * The returned set is backed by the original, so changes in one appear in 394 * the other. The subset will throw an {@link IllegalArgumentException} 395 * for any attempt to access or add an element beyond the specified cutoffs. 396 * 397 * @param from the low cutoff point 398 * @param fromInclusive true if <code>from</code> should be included. 399 * @param to the high cutoff point 400 * @param toInclusive true if <code>to</code> should be included. 401 * @return a view of the set for the specified range. 402 * @throws ClassCastException if either cutoff is not compatible with 403 * the comparator (or is not Comparable, for natural ordering) 404 * @throws NullPointerException if from or to is null, but the comparator 405 * does not tolerate null elements 406 * @throws IllegalArgumentException if from is greater than to 407 */ 408 public NavigableSet<T> subSet(T from, boolean fromInclusive, 409 T to, boolean toInclusive) 410 { 411 return new TreeSet<T>(map.subMap(from, fromInclusive, 412 to, toInclusive)); 413 } 414 415 /** 416 * Returns a view of this Set including all elements greater or equal to 417 * <code>from</code>. The returned set is backed by the original, so 418 * changes in one appear in the other. The subset will throw an 419 * {@link IllegalArgumentException} for any attempt to access or add an 420 * element beyond the specified cutoff. The returned set includes the 421 * endpoint; if you want to exclude it, pass in the successor element 422 * or call {@link #tailSet(T,boolean)}. This is equivalent to calling 423 * <code>tailSet(from, true)</code>. 424 * 425 * @param from the (inclusive) low cutoff point 426 * @return a view of the set above the cutoff 427 * @throws ClassCastException if <code>from</code> is not compatible with 428 * the comparator (or is not Comparable, for natural ordering) 429 * @throws NullPointerException if from is null, but the comparator 430 * does not tolerate null elements 431 */ 432 public SortedSet<T> tailSet(T from) 433 { 434 return tailSet(from, true); 435 } 436 437 /** 438 * Returns a view of this Set including all elements greater (or equal to, 439 * if <code>inclusive</code> is true) <code>from</code>. The returned set 440 * is backed by the original, so changes in one appear in the other. The 441 * subset will throw an {@link IllegalArgumentException} for any attempt 442 * to access or add an element beyond the specified cutoff. 443 * 444 * @param from the low cutoff point. 445 * @param inclusive true if <code>from</code> should be included. 446 * @return a view of the set for the specified range. 447 * @throws ClassCastException if <code>from</code> is not compatible with 448 * the comparator (or is not Comparable, for natural ordering) 449 * @throws NullPointerException if from is null, but the comparator 450 * does not tolerate null elements 451 */ 452 public NavigableSet<T> tailSet(T from, boolean inclusive) 453 { 454 return new TreeSet<T>(map.tailMap(from, inclusive)); 455 } 456 457 /** 458 * Serializes this object to the given stream. 459 * 460 * @param s the stream to write to 461 * @throws IOException if the underlying stream fails 462 * @serialData the <i>comparator</i> (Object), followed by the set size 463 * (int), the the elements in sorted order (Object) 464 */ 465 private void writeObject(ObjectOutputStream s) throws IOException 466 { 467 s.defaultWriteObject(); 468 Iterator<T> itr = map.keySet().iterator(); 469 int pos = map.size(); 470 s.writeObject(map.comparator()); 471 s.writeInt(pos); 472 while (--pos >= 0) 473 s.writeObject(itr.next()); 474 } 475 476 /** 477 * Deserializes this object from the given stream. 478 * 479 * @param s the stream to read from 480 * @throws ClassNotFoundException if the underlying stream fails 481 * @throws IOException if the underlying stream fails 482 * @serialData the <i>comparator</i> (Object), followed by the set size 483 * (int), the the elements in sorted order (Object) 484 */ 485 private void readObject(ObjectInputStream s) 486 throws IOException, ClassNotFoundException 487 { 488 s.defaultReadObject(); 489 Comparator<? super T> comparator = (Comparator<? super T>) s.readObject(); 490 int size = s.readInt(); 491 map = new TreeMap<T, String>(comparator); 492 ((TreeMap<T, String>) map).putFromObjStream(s, size, false); 493 } 494 495 /** 496 * Returns the least or lowest element in the set greater than or 497 * equal to the given element, or <code>null</code> if there is 498 * no such element. 499 * 500 * @param e the element relative to the returned element. 501 * @return the least element greater than or equal 502 * to the given element, or <code>null</code> if there is 503 * no such element. 504 * @throws ClassCastException if the specified element can not 505 * be compared with those in the map. 506 * @throws NullPointerException if the element is <code>null</code> 507 * and this set either uses natural 508 * ordering or a comparator that does 509 * not permit null elements. 510 * @since 1.6 511 */ 512 public T ceiling(T e) 513 { 514 return map.ceilingKey(e); 515 } 516 517 /** 518 * Returns an iterator over the elements of this set in descending 519 * order. This is equivalent to calling 520 * <code>descendingSet().iterator()</code>. 521 * 522 * @return an iterator over the elements in descending order. 523 * @since 1.6 524 */ 525 public Iterator<T> descendingIterator() 526 { 527 return descendingSet().iterator(); 528 } 529 530 /** 531 * Returns a view of the set in reverse order. The descending set 532 * is backed by the original set, so that changes affect both sets. 533 * Any changes occurring to either set while an iteration is taking 534 * place (with the exception of a {@link Iterator#remove()} operation) 535 * result in undefined behaviour from the iteration. The ordering 536 * of the descending set is the same as for a set with a 537 * {@link Comparator} given by {@link Collections#reverseOrder()}, 538 * and calling {@link #descendingSet()} on the descending set itself 539 * results in a view equivalent to the original set. 540 * 541 * @return a reverse order view of the set. 542 * @since 1.6 543 */ 544 public NavigableSet<T> descendingSet() 545 { 546 return map.descendingKeySet(); 547 } 548 549 /** 550 * Returns the greatest or highest element in the set less than or 551 * equal to the given element, or <code>null</code> if there is 552 * no such element. 553 * 554 * @param e the element relative to the returned element. 555 * @return the greatest element less than or equal 556 * to the given element, or <code>null</code> if there is 557 * no such element. 558 * @throws ClassCastException if the specified element can not 559 * be compared with those in the map. 560 * @throws NullPointerException if the element is <code>null</code> 561 * and this set either uses natural 562 * ordering or a comparator that does 563 * not permit null elements. 564 * @since 1.6 565 */ 566 public T floor(T e) 567 { 568 return map.floorKey(e); 569 } 570 571 /** 572 * Returns the least or lowest element in the set strictly greater 573 * than the given element, or <code>null</code> if there is 574 * no such element. 575 * 576 * @param e the element relative to the returned element. 577 * @return the least element greater than 578 * the given element, or <code>null</code> if there is 579 * no such element. 580 * @throws ClassCastException if the specified element can not 581 * be compared with those in the map. 582 * @throws NullPointerException if the element is <code>null</code> 583 * and this set either uses natural 584 * ordering or a comparator that does 585 * not permit null elements. 586 * @since 1.6 587 */ 588 public T higher(T e) 589 { 590 return map.higherKey(e); 591 } 592 593 /** 594 * Returns the greatest or highest element in the set strictly less 595 * than the given element, or <code>null</code> if there is 596 * no such element. 597 * 598 * @param e the element relative to the returned element. 599 * @return the greatest element less than 600 * the given element, or <code>null</code> if there is 601 * no such element. 602 * @throws ClassCastException if the specified element can not 603 * be compared with those in the map. 604 * @throws NullPointerException if the element is <code>null</code> 605 * and this set either uses natural 606 * ordering or a comparator that does 607 * not permit null elements. 608 * @since 1.6 609 */ 610 public T lower(T e) 611 { 612 return map.lowerKey(e); 613 } 614 615 /** 616 * Removes and returns the least or lowest element in the set, 617 * or <code>null</code> if the map is empty. 618 * 619 * @return the removed first element, or <code>null</code> if the 620 * map is empty. 621 * @since 1.6 622 */ 623 public T pollFirst() 624 { 625 return map.pollFirstEntry().getKey(); 626 } 627 628 /** 629 * Removes and returns the greatest or highest element in the set, 630 * or <code>null</code> if the map is empty. 631 * 632 * @return the removed last element, or <code>null</code> if the 633 * map is empty. 634 * @since 1.6 635 */ 636 public T pollLast() 637 { 638 return map.pollLastEntry().getKey(); 639 } 640 641}