1 /* 2 * Copyright (c) 1998, 2019, 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>This class is a member of the 77 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 78 * Java Collections Framework</a>. 79 * 80 * @param <E> the type of elements maintained by this set 81 * 82 * @author Josh Bloch 83 * @see Collection 84 * @see Set 85 * @see HashSet 86 * @see Comparable 87 * @see Comparator 88 * @see TreeMap 89 * @since 1.2 90 */ 91 92 public class TreeSet<E> extends AbstractSet<E> 93 implements NavigableSet<E>, Cloneable, java.io.Serializable 94 { 95 /** 96 * The backing map. 97 */ 98 private transient NavigableMap<E,Object> m; 99 100 // Dummy value to associate with an Object in the backing Map 101 private static final Object PRESENT = new Object(); 102 103 /** 104 * Constructs a set backed by the specified navigable map. 105 */ TreeSet(NavigableMap<E,Object> m)106 TreeSet(NavigableMap<E,Object> m) { 107 this.m = m; 108 } 109 110 /** 111 * Constructs a new, empty tree set, sorted according to the 112 * natural ordering of its elements. All elements inserted into 113 * the set must implement the {@link Comparable} interface. 114 * Furthermore, all such elements must be <i>mutually 115 * comparable</i>: {@code e1.compareTo(e2)} must not throw a 116 * {@code ClassCastException} for any elements {@code e1} and 117 * {@code e2} in the set. If the user attempts to add an element 118 * to the set that violates this constraint (for example, the user 119 * attempts to add a string element to a set whose elements are 120 * integers), the {@code add} call will throw a 121 * {@code ClassCastException}. 122 */ TreeSet()123 public TreeSet() { 124 this(new TreeMap<>()); 125 } 126 127 /** 128 * Constructs a new, empty tree set, sorted according to the specified 129 * comparator. All elements inserted into the set must be <i>mutually 130 * comparable</i> by the specified comparator: {@code comparator.compare(e1, 131 * e2)} must not throw a {@code ClassCastException} for any elements 132 * {@code e1} and {@code e2} in the set. If the user attempts to add 133 * an element to the set that violates this constraint, the 134 * {@code add} call will throw a {@code ClassCastException}. 135 * 136 * @param comparator the comparator that will be used to order this set. 137 * If {@code null}, the {@linkplain Comparable natural 138 * ordering} of the elements will be used. 139 */ TreeSet(Comparator<? super E> comparator)140 public TreeSet(Comparator<? super E> comparator) { 141 this(new TreeMap<>(comparator)); 142 } 143 144 /** 145 * Constructs a new tree set containing the elements in the specified 146 * collection, sorted according to the <i>natural ordering</i> of its 147 * elements. All elements inserted into the set must implement the 148 * {@link Comparable} interface. Furthermore, all such elements must be 149 * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a 150 * {@code ClassCastException} for any elements {@code e1} and 151 * {@code e2} in the set. 152 * 153 * @param c collection whose elements will comprise the new set 154 * @throws ClassCastException if the elements in {@code c} are 155 * not {@link Comparable}, or are not mutually comparable 156 * @throws NullPointerException if the specified collection is null 157 */ TreeSet(Collection<? extends E> c)158 public TreeSet(Collection<? extends E> c) { 159 this(); 160 addAll(c); 161 } 162 163 /** 164 * Constructs a new tree set containing the same elements and 165 * using the same ordering as the specified sorted set. 166 * 167 * @param s sorted set whose elements will comprise the new set 168 * @throws NullPointerException if the specified sorted set is null 169 */ TreeSet(SortedSet<E> s)170 public TreeSet(SortedSet<E> s) { 171 this(s.comparator()); 172 addAll(s); 173 } 174 175 /** 176 * Returns an iterator over the elements in this set in ascending order. 177 * 178 * @return an iterator over the elements in this set in ascending order 179 */ iterator()180 public Iterator<E> iterator() { 181 return m.navigableKeySet().iterator(); 182 } 183 184 /** 185 * Returns an iterator over the elements in this set in descending order. 186 * 187 * @return an iterator over the elements in this set in descending order 188 * @since 1.6 189 */ descendingIterator()190 public Iterator<E> descendingIterator() { 191 return m.descendingKeySet().iterator(); 192 } 193 194 /** 195 * @since 1.6 196 */ descendingSet()197 public NavigableSet<E> descendingSet() { 198 return new TreeSet<>(m.descendingMap()); 199 } 200 201 /** 202 * Returns the number of elements in this set (its cardinality). 203 * 204 * @return the number of elements in this set (its cardinality) 205 */ size()206 public int size() { 207 return m.size(); 208 } 209 210 /** 211 * Returns {@code true} if this set contains no elements. 212 * 213 * @return {@code true} if this set contains no elements 214 */ isEmpty()215 public boolean isEmpty() { 216 return m.isEmpty(); 217 } 218 219 /** 220 * Returns {@code true} if this set contains the specified element. 221 * More formally, returns {@code true} if and only if this set 222 * contains an element {@code e} such that 223 * {@code Objects.equals(o, e)}. 224 * 225 * @param o object to be checked for containment in this set 226 * @return {@code true} if this set contains the specified element 227 * @throws ClassCastException if the specified object cannot be compared 228 * with the elements currently in the set 229 * @throws NullPointerException if the specified element is null 230 * and this set uses natural ordering, or its comparator 231 * does not permit null elements 232 */ contains(Object o)233 public boolean contains(Object o) { 234 return m.containsKey(o); 235 } 236 237 /** 238 * Adds the specified element to this set if it is not already present. 239 * More formally, adds the specified element {@code e} to this set if 240 * the set contains no element {@code e2} such that 241 * {@code Objects.equals(e, e2)}. 242 * If this set already contains the element, the call leaves the set 243 * unchanged and returns {@code false}. 244 * 245 * @param e element to be added to this set 246 * @return {@code true} if this set did not already contain the specified 247 * element 248 * @throws ClassCastException if the specified object cannot be compared 249 * with the elements currently in this set 250 * @throws NullPointerException if the specified element is null 251 * and this set uses natural ordering, or its comparator 252 * does not permit null elements 253 */ add(E e)254 public boolean add(E e) { 255 return m.put(e, PRESENT)==null; 256 } 257 258 /** 259 * Removes the specified element from this set if it is present. 260 * More formally, removes an element {@code e} such that 261 * {@code Objects.equals(o, e)}, 262 * if this set contains such an element. Returns {@code true} if 263 * this set contained the element (or equivalently, if this set 264 * changed as a result of the call). (This set will not contain the 265 * element once the call returns.) 266 * 267 * @param o object to be removed from this set, if present 268 * @return {@code true} if this set contained the specified element 269 * @throws ClassCastException if the specified object cannot be compared 270 * with the elements currently in this set 271 * @throws NullPointerException if the specified element is null 272 * and this set uses natural ordering, or its comparator 273 * does not permit null elements 274 */ remove(Object o)275 public boolean remove(Object o) { 276 return m.remove(o)==PRESENT; 277 } 278 279 /** 280 * Removes all of the elements from this set. 281 * The set will be empty after this call returns. 282 */ clear()283 public void clear() { 284 m.clear(); 285 } 286 287 /** 288 * Adds all of the elements in the specified collection to this set. 289 * 290 * @param c collection containing elements to be added to this set 291 * @return {@code true} if this set changed as a result of the call 292 * @throws ClassCastException if the elements provided cannot be compared 293 * with the elements currently in the set 294 * @throws NullPointerException if the specified collection is null or 295 * if any element is null and this set uses natural ordering, or 296 * its comparator does not permit null elements 297 */ addAll(Collection<? extends E> c)298 public boolean addAll(Collection<? extends E> c) { 299 // Use linear-time version if applicable 300 if (m.size()==0 && c.size() > 0 && 301 c instanceof SortedSet && 302 m instanceof TreeMap<E, Object> map) { 303 SortedSet<? extends E> set = (SortedSet<? extends E>) c; 304 if (Objects.equals(set.comparator(), map.comparator())) { 305 map.addAllForTreeSet(set, PRESENT); 306 return true; 307 } 308 } 309 return super.addAll(c); 310 } 311 312 /** 313 * @throws ClassCastException {@inheritDoc} 314 * @throws NullPointerException if {@code fromElement} or {@code toElement} 315 * is null and this set uses natural ordering, or its comparator 316 * does not permit null elements 317 * @throws IllegalArgumentException {@inheritDoc} 318 * @since 1.6 319 */ subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)320 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, 321 E toElement, boolean toInclusive) { 322 return new TreeSet<>(m.subMap(fromElement, fromInclusive, 323 toElement, toInclusive)); 324 } 325 326 /** 327 * @throws ClassCastException {@inheritDoc} 328 * @throws NullPointerException if {@code toElement} is null and 329 * this set uses natural ordering, or its comparator does 330 * not permit null elements 331 * @throws IllegalArgumentException {@inheritDoc} 332 * @since 1.6 333 */ headSet(E toElement, boolean inclusive)334 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 335 return new TreeSet<>(m.headMap(toElement, inclusive)); 336 } 337 338 /** 339 * @throws ClassCastException {@inheritDoc} 340 * @throws NullPointerException if {@code fromElement} is null and 341 * this set uses natural ordering, or its comparator does 342 * not permit null elements 343 * @throws IllegalArgumentException {@inheritDoc} 344 * @since 1.6 345 */ tailSet(E fromElement, boolean inclusive)346 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 347 return new TreeSet<>(m.tailMap(fromElement, inclusive)); 348 } 349 350 /** 351 * @throws ClassCastException {@inheritDoc} 352 * @throws NullPointerException if {@code fromElement} or 353 * {@code toElement} is null and this set uses natural ordering, 354 * or its comparator does not permit null elements 355 * @throws IllegalArgumentException {@inheritDoc} 356 */ subSet(E fromElement, E toElement)357 public SortedSet<E> subSet(E fromElement, E toElement) { 358 return subSet(fromElement, true, toElement, false); 359 } 360 361 /** 362 * @throws ClassCastException {@inheritDoc} 363 * @throws NullPointerException if {@code toElement} is null 364 * and this set uses natural ordering, or its comparator does 365 * not permit null elements 366 * @throws IllegalArgumentException {@inheritDoc} 367 */ headSet(E toElement)368 public SortedSet<E> headSet(E toElement) { 369 return headSet(toElement, false); 370 } 371 372 /** 373 * @throws ClassCastException {@inheritDoc} 374 * @throws NullPointerException if {@code fromElement} is null 375 * and this set uses natural ordering, or its comparator does 376 * not permit null elements 377 * @throws IllegalArgumentException {@inheritDoc} 378 */ tailSet(E fromElement)379 public SortedSet<E> tailSet(E fromElement) { 380 return tailSet(fromElement, true); 381 } 382 comparator()383 public Comparator<? super E> comparator() { 384 return m.comparator(); 385 } 386 387 /** 388 * @throws NoSuchElementException {@inheritDoc} 389 */ first()390 public E first() { 391 return m.firstKey(); 392 } 393 394 /** 395 * @throws NoSuchElementException {@inheritDoc} 396 */ last()397 public E last() { 398 return m.lastKey(); 399 } 400 401 // NavigableSet API methods 402 403 /** 404 * @throws ClassCastException {@inheritDoc} 405 * @throws NullPointerException if the specified element is null 406 * and this set uses natural ordering, or its comparator 407 * does not permit null elements 408 * @since 1.6 409 */ lower(E e)410 public E lower(E e) { 411 return m.lowerKey(e); 412 } 413 414 /** 415 * @throws ClassCastException {@inheritDoc} 416 * @throws NullPointerException if the specified element is null 417 * and this set uses natural ordering, or its comparator 418 * does not permit null elements 419 * @since 1.6 420 */ floor(E e)421 public E floor(E e) { 422 return m.floorKey(e); 423 } 424 425 /** 426 * @throws ClassCastException {@inheritDoc} 427 * @throws NullPointerException if the specified element is null 428 * and this set uses natural ordering, or its comparator 429 * does not permit null elements 430 * @since 1.6 431 */ ceiling(E e)432 public E ceiling(E e) { 433 return m.ceilingKey(e); 434 } 435 436 /** 437 * @throws ClassCastException {@inheritDoc} 438 * @throws NullPointerException if the specified element is null 439 * and this set uses natural ordering, or its comparator 440 * does not permit null elements 441 * @since 1.6 442 */ higher(E e)443 public E higher(E e) { 444 return m.higherKey(e); 445 } 446 447 /** 448 * @since 1.6 449 */ pollFirst()450 public E pollFirst() { 451 Map.Entry<E,?> e = m.pollFirstEntry(); 452 return (e == null) ? null : e.getKey(); 453 } 454 455 /** 456 * @since 1.6 457 */ pollLast()458 public E pollLast() { 459 Map.Entry<E,?> e = m.pollLastEntry(); 460 return (e == null) ? null : e.getKey(); 461 } 462 463 /** 464 * Returns a shallow copy of this {@code TreeSet} instance. (The elements 465 * themselves are not cloned.) 466 * 467 * @return a shallow copy of this set 468 */ 469 @SuppressWarnings("unchecked") clone()470 public Object clone() { 471 TreeSet<E> clone; 472 try { 473 clone = (TreeSet<E>) super.clone(); 474 } catch (CloneNotSupportedException e) { 475 throw new InternalError(e); 476 } 477 478 clone.m = new TreeMap<>(m); 479 return clone; 480 } 481 482 /** 483 * Save the state of the {@code TreeSet} instance to a stream (that is, 484 * serialize it). 485 * 486 * @serialData Emits the comparator used to order this set, or 487 * {@code null} if it obeys its elements' natural ordering 488 * (Object), followed by the size of the set (the number of 489 * elements it contains) (int), followed by all of its 490 * elements (each an Object) in order (as determined by the 491 * set's Comparator, or by the elements' natural ordering if 492 * the set has no Comparator). 493 */ 494 @java.io.Serial writeObject(java.io.ObjectOutputStream s)495 private void writeObject(java.io.ObjectOutputStream s) 496 throws java.io.IOException { 497 // Write out any hidden stuff 498 s.defaultWriteObject(); 499 500 // Write out Comparator 501 s.writeObject(m.comparator()); 502 503 // Write out size 504 s.writeInt(m.size()); 505 506 // Write out all elements in the proper order. 507 for (E e : m.keySet()) 508 s.writeObject(e); 509 } 510 511 /** 512 * Reconstitute the {@code TreeSet} instance from a stream (that is, 513 * deserialize it). 514 */ 515 @java.io.Serial readObject(java.io.ObjectInputStream s)516 private void readObject(java.io.ObjectInputStream s) 517 throws java.io.IOException, ClassNotFoundException { 518 // Read in any hidden stuff 519 s.defaultReadObject(); 520 521 // Read in Comparator 522 @SuppressWarnings("unchecked") 523 Comparator<? super E> c = (Comparator<? super E>) s.readObject(); 524 525 // Create backing TreeMap 526 TreeMap<E,Object> tm = new TreeMap<>(c); 527 m = tm; 528 529 // Read in size 530 int size = s.readInt(); 531 532 tm.readTreeSet(size, s, PRESENT); 533 } 534 535 /** 536 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 537 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 538 * set. 539 * 540 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 541 * {@link Spliterator#DISTINCT}, {@link Spliterator#SORTED}, and 542 * {@link Spliterator#ORDERED}. Overriding implementations should document 543 * the reporting of additional characteristic values. 544 * 545 * <p>The spliterator's comparator (see 546 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 547 * the tree set's comparator (see {@link #comparator()}) is {@code null}. 548 * Otherwise, the spliterator's comparator is the same as or imposes the 549 * same total ordering as the tree set's comparator. 550 * 551 * @return a {@code Spliterator} over the elements in this set 552 * @since 1.8 553 */ spliterator()554 public Spliterator<E> spliterator() { 555 return TreeMap.keySpliteratorFor(m); 556 } 557 558 @java.io.Serial 559 private static final long serialVersionUID = -2479143000061671589L; 560 } 561