1 /* 2 * Copyright (c) 1998, 2023, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 /** 29 * A {@link NavigableSet} implementation based on a {@link TreeMap}. 30 * The elements are ordered using their {@linkplain Comparable natural 31 * ordering}, or by a {@link Comparator} provided at set creation 32 * time, depending on which constructor is used. 33 * 34 * <p>This implementation provides guaranteed log(n) time cost for the basic 35 * operations ({@code add}, {@code remove} and {@code contains}). 36 * 37 * <p>Note that the ordering maintained by a set (whether or not an explicit 38 * comparator is provided) must be <i>consistent with equals</i> if it is to 39 * correctly implement the {@code Set} interface. (See {@code Comparable} 40 * or {@code Comparator} for a precise definition of <i>consistent with 41 * equals</i>.) This is so because the {@code Set} interface is defined in 42 * terms of the {@code equals} operation, but a {@code TreeSet} instance 43 * performs all element comparisons using its {@code compareTo} (or 44 * {@code compare}) method, so two elements that are deemed equal by this method 45 * are, from the standpoint of the set, equal. The behavior of a set 46 * <i>is</i> well-defined even if its ordering is inconsistent with equals; it 47 * just fails to obey the general contract of the {@code Set} interface. 48 * 49 * <p><strong>Note that this implementation is not synchronized.</strong> 50 * If multiple threads access a tree set concurrently, and at least one 51 * of the threads modifies the set, it <i>must</i> be synchronized 52 * externally. This is typically accomplished by synchronizing on some 53 * object that naturally encapsulates the set. 54 * If no such object exists, the set should be "wrapped" using the 55 * {@link Collections#synchronizedSortedSet Collections.synchronizedSortedSet} 56 * method. This is best done at creation time, to prevent accidental 57 * unsynchronized access to the set: <pre> 58 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));</pre> 59 * 60 * <p>The iterators returned by this class's {@code iterator} method are 61 * <i>fail-fast</i>: if the set is modified at any time after the iterator is 62 * created, in any way except through the iterator's own {@code remove} 63 * method, the iterator will throw a {@link ConcurrentModificationException}. 64 * Thus, in the face of concurrent modification, the iterator fails quickly 65 * and cleanly, rather than risking arbitrary, non-deterministic behavior at 66 * an undetermined time in the future. 67 * 68 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 69 * as it is, generally speaking, impossible to make any hard guarantees in the 70 * presence of unsynchronized concurrent modification. Fail-fast iterators 71 * throw {@code ConcurrentModificationException} on a best-effort basis. 72 * Therefore, it would be wrong to write a program that depended on this 73 * exception for its correctness: <i>the fail-fast behavior of iterators 74 * should be used only to detect bugs.</i> 75 * 76 * <p>The {@link #addFirst addFirst} and {@link #addLast addLast} methods of this class 77 * throw {@code UnsupportedOperationException}. The encounter order of elements is determined 78 * by the comparison method; therefore, explicit positioning is not supported. 79 * 80 * <p>This class is a member of the 81 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 82 * Java Collections Framework</a>. 83 * 84 * @param <E> the type of elements maintained by this set 85 * 86 * @author Josh Bloch 87 * @see Collection 88 * @see Set 89 * @see HashSet 90 * @see Comparable 91 * @see Comparator 92 * @see TreeMap 93 * @since 1.2 94 */ 95 96 public class TreeSet<E> extends AbstractSet<E> 97 implements NavigableSet<E>, Cloneable, java.io.Serializable 98 { 99 /** 100 * The backing map. 101 */ 102 private transient NavigableMap<E,Object> m; 103 104 // Dummy value to associate with an Object in the backing Map 105 private static final Object PRESENT = new Object(); 106 107 /** 108 * Constructs a set backed by the specified navigable map. 109 */ TreeSet(NavigableMap<E,Object> m)110 TreeSet(NavigableMap<E,Object> m) { 111 this.m = m; 112 } 113 114 /** 115 * Constructs a new, empty tree set, sorted according to the 116 * natural ordering of its elements. All elements inserted into 117 * the set must implement the {@link Comparable} interface. 118 * Furthermore, all such elements must be <i>mutually 119 * comparable</i>: {@code e1.compareTo(e2)} must not throw a 120 * {@code ClassCastException} for any elements {@code e1} and 121 * {@code e2} in the set. If the user attempts to add an element 122 * to the set that violates this constraint (for example, the user 123 * attempts to add a string element to a set whose elements are 124 * integers), the {@code add} call will throw a 125 * {@code ClassCastException}. 126 */ TreeSet()127 public TreeSet() { 128 this(new TreeMap<>()); 129 } 130 131 /** 132 * Constructs a new, empty tree set, sorted according to the specified 133 * comparator. All elements inserted into the set must be <i>mutually 134 * comparable</i> by the specified comparator: {@code comparator.compare(e1, 135 * e2)} must not throw a {@code ClassCastException} for any elements 136 * {@code e1} and {@code e2} in the set. If the user attempts to add 137 * an element to the set that violates this constraint, the 138 * {@code add} call will throw a {@code ClassCastException}. 139 * 140 * @param comparator the comparator that will be used to order this set. 141 * If {@code null}, the {@linkplain Comparable natural 142 * ordering} of the elements will be used. 143 */ TreeSet(Comparator<? super E> comparator)144 public TreeSet(Comparator<? super E> comparator) { 145 this(new TreeMap<>(comparator)); 146 } 147 148 /** 149 * Constructs a new tree set containing the elements in the specified 150 * collection, sorted according to the <i>natural ordering</i> of its 151 * elements. All elements inserted into the set must implement the 152 * {@link Comparable} interface. Furthermore, all such elements must be 153 * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a 154 * {@code ClassCastException} for any elements {@code e1} and 155 * {@code e2} in the set. 156 * 157 * @param c collection whose elements will comprise the new set 158 * @throws ClassCastException if the elements in {@code c} are 159 * not {@link Comparable}, or are not mutually comparable 160 * @throws NullPointerException if the specified collection is null 161 */ TreeSet(Collection<? extends E> c)162 public TreeSet(Collection<? extends E> c) { 163 this(); 164 addAll(c); 165 } 166 167 /** 168 * Constructs a new tree set containing the same elements and 169 * using the same ordering as the specified sorted set. 170 * 171 * @param s sorted set whose elements will comprise the new set 172 * @throws NullPointerException if the specified sorted set is null 173 */ TreeSet(SortedSet<E> s)174 public TreeSet(SortedSet<E> s) { 175 this(s.comparator()); 176 addAll(s); 177 } 178 179 /** 180 * Returns an iterator over the elements in this set in ascending order. 181 * 182 * @return an iterator over the elements in this set in ascending order 183 */ iterator()184 public Iterator<E> iterator() { 185 return m.navigableKeySet().iterator(); 186 } 187 188 /** 189 * Returns an iterator over the elements in this set in descending order. 190 * 191 * @return an iterator over the elements in this set in descending order 192 * @since 1.6 193 */ descendingIterator()194 public Iterator<E> descendingIterator() { 195 return m.descendingKeySet().iterator(); 196 } 197 198 /** 199 * @since 1.6 200 */ descendingSet()201 public NavigableSet<E> descendingSet() { 202 return new TreeSet<>(m.descendingMap()); 203 } 204 205 /** 206 * Returns the number of elements in this set (its cardinality). 207 * 208 * @return the number of elements in this set (its cardinality) 209 */ size()210 public int size() { 211 return m.size(); 212 } 213 214 /** 215 * Returns {@code true} if this set contains no elements. 216 * 217 * @return {@code true} if this set contains no elements 218 */ isEmpty()219 public boolean isEmpty() { 220 return m.isEmpty(); 221 } 222 223 /** 224 * Returns {@code true} if this set contains the specified element. 225 * More formally, returns {@code true} if and only if this set 226 * contains an element {@code e} such that 227 * {@code Objects.equals(o, e)}. 228 * 229 * @param o object to be checked for containment in this set 230 * @return {@code true} if this set contains the specified element 231 * @throws ClassCastException if the specified object cannot be compared 232 * with the elements currently in the set 233 * @throws NullPointerException if the specified element is null 234 * and this set uses natural ordering, or its comparator 235 * does not permit null elements 236 */ contains(Object o)237 public boolean contains(Object o) { 238 return m.containsKey(o); 239 } 240 241 /** 242 * Adds the specified element to this set if it is not already present. 243 * More formally, adds the specified element {@code e} to this set if 244 * the set contains no element {@code e2} such that 245 * {@code Objects.equals(e, e2)}. 246 * If this set already contains the element, the call leaves the set 247 * unchanged and returns {@code false}. 248 * 249 * @param e element to be added to this set 250 * @return {@code true} if this set did not already contain the specified 251 * element 252 * @throws ClassCastException if the specified object cannot be compared 253 * with the elements currently in this set 254 * @throws NullPointerException if the specified element is null 255 * and this set uses natural ordering, or its comparator 256 * does not permit null elements 257 */ add(E e)258 public boolean add(E e) { 259 return m.put(e, PRESENT)==null; 260 } 261 262 /** 263 * Removes the specified element from this set if it is present. 264 * More formally, removes an element {@code e} such that 265 * {@code Objects.equals(o, e)}, 266 * if this set contains such an element. Returns {@code true} if 267 * this set contained the element (or equivalently, if this set 268 * changed as a result of the call). (This set will not contain the 269 * element once the call returns.) 270 * 271 * @param o object to be removed from this set, if present 272 * @return {@code true} if this set contained the specified element 273 * @throws ClassCastException if the specified object cannot be compared 274 * with the elements currently in this set 275 * @throws NullPointerException if the specified element is null 276 * and this set uses natural ordering, or its comparator 277 * does not permit null elements 278 */ remove(Object o)279 public boolean remove(Object o) { 280 return m.remove(o)==PRESENT; 281 } 282 283 /** 284 * Removes all of the elements from this set. 285 * The set will be empty after this call returns. 286 */ clear()287 public void clear() { 288 m.clear(); 289 } 290 291 /** 292 * Adds all of the elements in the specified collection to this set. 293 * 294 * @param c collection containing elements to be added to this set 295 * @return {@code true} if this set changed as a result of the call 296 * @throws ClassCastException if the elements provided cannot be compared 297 * with the elements currently in the set 298 * @throws NullPointerException if the specified collection is null or 299 * if any element is null and this set uses natural ordering, or 300 * its comparator does not permit null elements 301 */ addAll(Collection<? extends E> c)302 public boolean addAll(Collection<? extends E> c) { 303 // Use linear-time version if applicable 304 if (m.size()==0 && c.size() > 0 && 305 c instanceof SortedSet && 306 m instanceof TreeMap<E, Object> map) { 307 SortedSet<? extends E> set = (SortedSet<? extends E>) c; 308 if (Objects.equals(set.comparator(), map.comparator())) { 309 map.addAllForTreeSet(set, PRESENT); 310 return true; 311 } 312 } 313 return super.addAll(c); 314 } 315 316 /** 317 * @throws ClassCastException {@inheritDoc} 318 * @throws NullPointerException if {@code fromElement} or {@code toElement} 319 * is null and this set uses natural ordering, or its comparator 320 * does not permit null elements 321 * @throws IllegalArgumentException {@inheritDoc} 322 * @since 1.6 323 */ subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)324 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, 325 E toElement, boolean toInclusive) { 326 return new TreeSet<>(m.subMap(fromElement, fromInclusive, 327 toElement, toInclusive)); 328 } 329 330 /** 331 * @throws ClassCastException {@inheritDoc} 332 * @throws NullPointerException if {@code toElement} is null and 333 * this set uses natural ordering, or its comparator does 334 * not permit null elements 335 * @throws IllegalArgumentException {@inheritDoc} 336 * @since 1.6 337 */ headSet(E toElement, boolean inclusive)338 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 339 return new TreeSet<>(m.headMap(toElement, inclusive)); 340 } 341 342 /** 343 * @throws ClassCastException {@inheritDoc} 344 * @throws NullPointerException if {@code fromElement} is null and 345 * this set uses natural ordering, or its comparator does 346 * not permit null elements 347 * @throws IllegalArgumentException {@inheritDoc} 348 * @since 1.6 349 */ tailSet(E fromElement, boolean inclusive)350 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 351 return new TreeSet<>(m.tailMap(fromElement, inclusive)); 352 } 353 354 /** 355 * @throws ClassCastException {@inheritDoc} 356 * @throws NullPointerException if {@code fromElement} or 357 * {@code toElement} is null and this set uses natural ordering, 358 * or its comparator does not permit null elements 359 * @throws IllegalArgumentException {@inheritDoc} 360 */ subSet(E fromElement, E toElement)361 public SortedSet<E> subSet(E fromElement, E toElement) { 362 return subSet(fromElement, true, toElement, false); 363 } 364 365 /** 366 * @throws ClassCastException {@inheritDoc} 367 * @throws NullPointerException if {@code toElement} is null 368 * and this set uses natural ordering, or its comparator does 369 * not permit null elements 370 * @throws IllegalArgumentException {@inheritDoc} 371 */ headSet(E toElement)372 public SortedSet<E> headSet(E toElement) { 373 return headSet(toElement, false); 374 } 375 376 /** 377 * @throws ClassCastException {@inheritDoc} 378 * @throws NullPointerException if {@code fromElement} is null 379 * and this set uses natural ordering, or its comparator does 380 * not permit null elements 381 * @throws IllegalArgumentException {@inheritDoc} 382 */ tailSet(E fromElement)383 public SortedSet<E> tailSet(E fromElement) { 384 return tailSet(fromElement, true); 385 } 386 comparator()387 public Comparator<? super E> comparator() { 388 return m.comparator(); 389 } 390 391 /** 392 * @throws NoSuchElementException {@inheritDoc} 393 */ first()394 public E first() { 395 return m.firstKey(); 396 } 397 398 /** 399 * @throws NoSuchElementException {@inheritDoc} 400 */ last()401 public E last() { 402 return m.lastKey(); 403 } 404 405 // NavigableSet API methods 406 407 /** 408 * @throws ClassCastException {@inheritDoc} 409 * @throws NullPointerException if the specified element is null 410 * and this set uses natural ordering, or its comparator 411 * does not permit null elements 412 * @since 1.6 413 */ lower(E e)414 public E lower(E e) { 415 return m.lowerKey(e); 416 } 417 418 /** 419 * @throws ClassCastException {@inheritDoc} 420 * @throws NullPointerException if the specified element is null 421 * and this set uses natural ordering, or its comparator 422 * does not permit null elements 423 * @since 1.6 424 */ floor(E e)425 public E floor(E e) { 426 return m.floorKey(e); 427 } 428 429 /** 430 * @throws ClassCastException {@inheritDoc} 431 * @throws NullPointerException if the specified element is null 432 * and this set uses natural ordering, or its comparator 433 * does not permit null elements 434 * @since 1.6 435 */ ceiling(E e)436 public E ceiling(E e) { 437 return m.ceilingKey(e); 438 } 439 440 /** 441 * @throws ClassCastException {@inheritDoc} 442 * @throws NullPointerException if the specified element is null 443 * and this set uses natural ordering, or its comparator 444 * does not permit null elements 445 * @since 1.6 446 */ higher(E e)447 public E higher(E e) { 448 return m.higherKey(e); 449 } 450 451 /** 452 * @since 1.6 453 */ pollFirst()454 public E pollFirst() { 455 Map.Entry<E,?> e = m.pollFirstEntry(); 456 return (e == null) ? null : e.getKey(); 457 } 458 459 /** 460 * @since 1.6 461 */ pollLast()462 public E pollLast() { 463 Map.Entry<E,?> e = m.pollLastEntry(); 464 return (e == null) ? null : e.getKey(); 465 } 466 467 /** 468 * Throws {@code UnsupportedOperationException}. The encounter order induced by this 469 * set's comparison method determines the position of elements, so explicit positioning 470 * is not supported. 471 * 472 * @throws UnsupportedOperationException always 473 * @since 21 474 */ addFirst(E e)475 public void addFirst(E e) { 476 throw new UnsupportedOperationException(); 477 } 478 479 /** 480 * Throws {@code UnsupportedOperationException}. The encounter order induced by this 481 * set's comparison method determines the position of elements, so explicit positioning 482 * is not supported. 483 * 484 * @throws UnsupportedOperationException always 485 * @since 21 486 */ addLast(E e)487 public void addLast(E e) { 488 throw new UnsupportedOperationException(); 489 } 490 491 /** 492 * Returns a shallow copy of this {@code TreeSet} instance. (The elements 493 * themselves are not cloned.) 494 * 495 * @return a shallow copy of this set 496 */ 497 @SuppressWarnings("unchecked") clone()498 public Object clone() { 499 TreeSet<E> clone; 500 try { 501 clone = (TreeSet<E>) super.clone(); 502 } catch (CloneNotSupportedException e) { 503 throw new InternalError(e); 504 } 505 506 clone.m = new TreeMap<>(m); 507 return clone; 508 } 509 510 /** 511 * Save the state of the {@code TreeSet} instance to a stream (that is, 512 * serialize it). 513 * 514 * @serialData Emits the comparator used to order this set, or 515 * {@code null} if it obeys its elements' natural ordering 516 * (Object), followed by the size of the set (the number of 517 * elements it contains) (int), followed by all of its 518 * elements (each an Object) in order (as determined by the 519 * set's Comparator, or by the elements' natural ordering if 520 * the set has no Comparator). 521 */ 522 @java.io.Serial writeObject(java.io.ObjectOutputStream s)523 private void writeObject(java.io.ObjectOutputStream s) 524 throws java.io.IOException { 525 // Write out any hidden stuff 526 s.defaultWriteObject(); 527 528 // Write out Comparator 529 s.writeObject(m.comparator()); 530 531 // Write out size 532 s.writeInt(m.size()); 533 534 // Write out all elements in the proper order. 535 for (E e : m.keySet()) 536 s.writeObject(e); 537 } 538 539 /** 540 * Reconstitute the {@code TreeSet} instance from a stream (that is, 541 * deserialize it). 542 */ 543 @java.io.Serial readObject(java.io.ObjectInputStream s)544 private void readObject(java.io.ObjectInputStream s) 545 throws java.io.IOException, ClassNotFoundException { 546 // Read in any hidden stuff 547 s.defaultReadObject(); 548 549 // Read in Comparator 550 @SuppressWarnings("unchecked") 551 Comparator<? super E> c = (Comparator<? super E>) s.readObject(); 552 553 // Create backing TreeMap 554 TreeMap<E,Object> tm = new TreeMap<>(c); 555 m = tm; 556 557 // Read in size 558 int size = s.readInt(); 559 560 tm.readTreeSet(size, s, PRESENT); 561 } 562 563 /** 564 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 565 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 566 * set. 567 * 568 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 569 * {@link Spliterator#DISTINCT}, {@link Spliterator#SORTED}, and 570 * {@link Spliterator#ORDERED}. Overriding implementations should document 571 * the reporting of additional characteristic values. 572 * 573 * <p>The spliterator's comparator (see 574 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 575 * the tree set's comparator (see {@link #comparator()}) is {@code null}. 576 * Otherwise, the spliterator's comparator is the same as or imposes the 577 * same total ordering as the tree set's comparator. 578 * 579 * @return a {@code Spliterator} over the elements in this set 580 * @since 1.8 581 */ spliterator()582 public Spliterator<E> spliterator() { 583 return TreeMap.keySpliteratorFor(m); 584 } 585 586 @java.io.Serial 587 private static final long serialVersionUID = -2479143000061671589L; 588 } 589