ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/TreeSet.java
(Generate patch)

Comparing jsr166/src/main/java/util/TreeSet.java (file contents):
Revision 1.20 by jsr166, Tue Feb 7 20:54:24 2006 UTC vs.
Revision 1.21 by dl, Wed Apr 19 15:07:14 2006 UTC

# Line 14 | Line 14 | package java.util;
14   * time, depending on which constructor is used.
15   *
16   * <p>This implementation provides guaranteed log(n) time cost for the basic
17 < * operations (<tt>add</tt>, <tt>remove</tt> and <tt>contains</tt>).
17 > * operations ({@code add}, {@code remove} and {@code contains}).
18   *
19   * <p>Note that the ordering maintained by a set (whether or not an explicit
20   * comparator is provided) must be <i>consistent with equals</i> if it is to
21 < * correctly implement the <tt>Set</tt> interface.  (See <tt>Comparable</tt>
22 < * or <tt>Comparator</tt> for a precise definition of <i>consistent with
23 < * equals</i>.)  This is so because the <tt>Set</tt> interface is defined in
24 < * terms of the <tt>equals</tt> operation, but a <tt>TreeSet</tt> instance
25 < * performs all element comparisons using its <tt>compareTo</tt> (or
26 < * <tt>compare</tt>) method, so two elements that are deemed equal by this method
21 > * correctly implement the {@code Set} interface.  (See {@code Comparable}
22 > * or {@code Comparator} for a precise definition of <i>consistent with
23 > * equals</i>.)  This is so because the {@code Set} interface is defined in
24 > * terms of the {@code equals} operation, but a {@code TreeSet} instance
25 > * performs all element comparisons using its {@code compareTo} (or
26 > * {@code compare}) method, so two elements that are deemed equal by this method
27   * are, from the standpoint of the set, equal.  The behavior of a set
28   * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
29 < * just fails to obey the general contract of the <tt>Set</tt> interface.
29 > * just fails to obey the general contract of the {@code Set} interface.
30   *
31   * <p><strong>Note that this implementation is not synchronized.</strong>
32   * If multiple threads access a tree set concurrently, and at least one
# Line 39 | Line 39 | package java.util;
39   * unsynchronized access to the set: <pre>
40   *   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));</pre>
41   *
42 < * <p>The iterators returned by this class's <tt>iterator</tt> method are
42 > * <p>The iterators returned by this class's {@code iterator} method are
43   * <i>fail-fast</i>: if the set is modified at any time after the iterator is
44 < * created, in any way except through the iterator's own <tt>remove</tt>
44 > * created, in any way except through the iterator's own {@code remove}
45   * method, the iterator will throw a {@link ConcurrentModificationException}.
46   * Thus, in the face of concurrent modification, the iterator fails quickly
47   * and cleanly, rather than risking arbitrary, non-deterministic behavior at
# Line 50 | Line 50 | package java.util;
50   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
51   * as it is, generally speaking, impossible to make any hard guarantees in the
52   * presence of unsynchronized concurrent modification.  Fail-fast iterators
53 < * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
53 > * throw {@code ConcurrentModificationException} on a best-effort basis.
54   * Therefore, it would be wrong to write a program that depended on this
55   * exception for its correctness:   <i>the fail-fast behavior of iterators
56   * should be used only to detect bugs.</i>
# Line 72 | Line 72 | package java.util;
72   * @since   1.2
73   */
74  
75 < public class TreeSet<E>
76 <    extends AbstractSet<E>
75 > public class TreeSet<E> extends AbstractSet<E>
76      implements NavigableSet<E>, Cloneable, java.io.Serializable
77   {
78 <    private transient NavigableMap<E,Object> m; // The backing Map
78 >    /**
79 >     * The backing map.
80 >     */
81 >    private transient NavigableMap<E,Object> m;
82  
83      // Dummy value to associate with an Object in the backing Map
84      private static final Object PRESENT = new Object();
# Line 84 | Line 86 | public class TreeSet<E>
86      /**
87       * Constructs a set backed by the specified navigable map.
88       */
89 <    private TreeSet(NavigableMap<E,Object> m) {
89 >    TreeSet(NavigableMap<E,Object> m) {
90          this.m = m;
91      }
92  
# Line 93 | Line 95 | public class TreeSet<E>
95       * natural ordering of its elements.  All elements inserted into
96       * the set must implement the {@link Comparable} interface.
97       * Furthermore, all such elements must be <i>mutually
98 <     * comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
99 <     * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
100 <     * <tt>e2</tt> in the set.  If the user attempts to add an element
98 >     * comparable</i>: {@code e1.compareTo(e2)} must not throw a
99 >     * {@code ClassCastException} for any elements {@code e1} and
100 >     * {@code e2} in the set.  If the user attempts to add an element
101       * to the set that violates this constraint (for example, the user
102       * attempts to add a string element to a set whose elements are
103 <     * integers), the <tt>add(Object)</tt> call will throw a
104 <     * <tt>ClassCastException</tt>.
103 >     * integers), the {@code add(Object)} call will throw a
104 >     * {@code ClassCastException}.
105       */
106      public TreeSet() {
107          this(new TreeMap<E,Object>());
# Line 108 | Line 110 | public class TreeSet<E>
110      /**
111       * Constructs a new, empty tree set, sorted according to the specified
112       * comparator.  All elements inserted into the set must be <i>mutually
113 <     * comparable</i> by the specified comparator: <tt>comparator.compare(e1,
114 <     * e2)</tt> must not throw a <tt>ClassCastException</tt> for any elements
115 <     * <tt>e1</tt> and <tt>e2</tt> in the set.  If the user attempts to add
113 >     * comparable</i> by the specified comparator: {@code comparator.compare(e1,
114 >     * e2)} must not throw a {@code ClassCastException} for any elements
115 >     * {@code e1} and {@code e2} in the set.  If the user attempts to add
116       * an element to the set that violates this constraint, the
117 <     * <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
117 >     * {@code add(Object)} call will throw a {@code ClassCastException}.
118       *
119       * @param comparator the comparator that will be used to order this set.
120 <     *        If <tt>null</tt>, the {@linkplain Comparable natural
120 >     *        If {@code null}, the {@linkplain Comparable natural
121       *        ordering} of the elements will be used.
122       */
123      public TreeSet(Comparator<? super E> comparator) {
# Line 127 | Line 129 | public class TreeSet<E>
129       * collection, sorted according to the <i>natural ordering</i> of its
130       * elements.  All elements inserted into the set must implement the
131       * {@link Comparable} interface.  Furthermore, all such elements must be
132 <     * <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
133 <     * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
134 <     * <tt>e2</tt> in the set.
132 >     * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
133 >     * {@code ClassCastException} for any elements {@code e1} and
134 >     * {@code e2} in the set.
135       *
136       * @param c collection whose elements will comprise the new set
137 <     * @throws ClassCastException if the elements in <tt>c</tt> are
137 >     * @throws ClassCastException if the elements in {@code c} are
138       *         not {@link Comparable}, or are not mutually comparable
139       * @throws NullPointerException if the specified collection is null
140       */
# Line 159 | Line 161 | public class TreeSet<E>
161       * @return an iterator over the elements in this set in ascending order
162       */
163      public Iterator<E> iterator() {
164 <        return m.keySet().iterator();
164 >        return m.navigableKeySet().iterator();
165      }
166  
167      /**
# Line 173 | Line 175 | public class TreeSet<E>
175      }
176  
177      /**
178 +     * @since 1.6
179 +     */
180 +    public NavigableSet<E> descendingSet() {
181 +        return new TreeSet(m.descendingMap());
182 +    }
183 +
184 +    /**
185       * Returns the number of elements in this set (its cardinality).
186       *
187       * @return the number of elements in this set (its cardinality)
# Line 182 | Line 191 | public class TreeSet<E>
191      }
192  
193      /**
194 <     * Returns <tt>true</tt> if this set contains no elements.
194 >     * Returns {@code true} if this set contains no elements.
195       *
196 <     * @return <tt>true</tt> if this set contains no elements
196 >     * @return {@code true} if this set contains no elements
197       */
198      public boolean isEmpty() {
199          return m.isEmpty();
200      }
201  
202      /**
203 <     * Returns <tt>true</tt> if this set contains the specified element.
204 <     * More formally, returns <tt>true</tt> if and only if this set
205 <     * contains an element <tt>e</tt> such that
206 <     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
203 >     * Returns {@code true} if this set contains the specified element.
204 >     * More formally, returns {@code true} if and only if this set
205 >     * contains an element {@code e} such that
206 >     * {@code (o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))}.
207       *
208       * @param o object to be checked for containment in this set
209 <     * @return <tt>true</tt> if this set contains the specified element
209 >     * @return {@code true} if this set contains the specified element
210       * @throws ClassCastException if the specified object cannot be compared
211       *         with the elements currently in the set
212       * @throws NullPointerException if the specified element is null
# Line 210 | Line 219 | public class TreeSet<E>
219  
220      /**
221       * Adds the specified element to this set if it is not already present.
222 <     * More formally, adds the specified element <tt>e</tt> to this set if
223 <     * the set contains no element <tt>e2</tt> such that
224 <     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
222 >     * More formally, adds the specified element {@code e} to this set if
223 >     * the set contains no element {@code e2} such that
224 >     * {@code (e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))}.
225       * If this set already contains the element, the call leaves the set
226 <     * unchanged and returns <tt>false</tt>.
226 >     * unchanged and returns {@code false}.
227       *
228       * @param e element to be added to this set
229 <     * @return <tt>true</tt> if this set did not already contain the specified
229 >     * @return {@code true} if this set did not already contain the specified
230       *         element
231       * @throws ClassCastException if the specified object cannot be compared
232       *         with the elements currently in this set
# Line 231 | Line 240 | public class TreeSet<E>
240  
241      /**
242       * Removes the specified element from this set if it is present.
243 <     * More formally, removes an element <tt>e</tt> such that
244 <     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
245 <     * if this set contains such an element.  Returns <tt>true</tt> if
243 >     * More formally, removes an element {@code e} such that
244 >     * {@code (o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))},
245 >     * if this set contains such an element.  Returns {@code true} if
246       * this set contained the element (or equivalently, if this set
247       * changed as a result of the call).  (This set will not contain the
248       * element once the call returns.)
249       *
250       * @param o object to be removed from this set, if present
251 <     * @return <tt>true</tt> if this set contained the specified element
251 >     * @return {@code true} if this set contained the specified 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
# Line 262 | Line 271 | public class TreeSet<E>
271       * Adds all of the elements in the specified collection to this set.
272       *
273       * @param c collection containing elements to be added to this set
274 <     * @return <tt>true</tt> if this set changed as a result of the call
274 >     * @return {@code true} if this set changed as a result of the call
275       * @throws ClassCastException if the elements provided cannot be compared
276       *         with the elements currently in the set
277       * @throws NullPointerException if the specified collection is null or
# Line 288 | Line 297 | public class TreeSet<E>
297  
298      /**
299       * @throws ClassCastException {@inheritDoc}
300 <     * @throws NullPointerException if <tt>fromElement</tt> or
301 <     *         <tt>toElement</tt> is null and this set uses natural ordering,
302 <     *         or its comparator does not permit null elements
300 >     * @throws NullPointerException if {@code fromElement} or {@code toElement}
301 >     *         is null and this set uses natural ordering, or its comparator
302 >     *         does not permit null elements
303       * @throws IllegalArgumentException {@inheritDoc}
304       * @since 1.6
305       */
306 <    public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
307 <        return new TreeSet<E>(m.navigableSubMap(fromElement, toElement));
306 >    public NavigableSet<E> navigableSubSet(E fromElement, boolean fromInclusive,
307 >                                           E toElement,   boolean toInclusive) {
308 >        return new TreeSet<E>(m.navigableSubMap(fromElement, fromInclusive,
309 >                                                toElement,   toInclusive));
310      }
311  
312      /**
313       * @throws ClassCastException {@inheritDoc}
314 <     * @throws NullPointerException if <tt>toElement</tt> is null and
314 >     * @throws NullPointerException if {@code toElement} is null and
315       *         this set uses natural ordering, or its comparator does
316       *         not permit null elements
317       * @throws IllegalArgumentException {@inheritDoc}
318       * @since 1.6
319       */
320 <    public NavigableSet<E> navigableHeadSet(E toElement) {
321 <        return new TreeSet<E>(m.navigableHeadMap(toElement));
320 >    public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
321 >        return new TreeSet<E>(m.navigableHeadMap(toElement, inclusive));
322      }
323  
324      /**
325       * @throws ClassCastException {@inheritDoc}
326 <     * @throws NullPointerException if <tt>fromElement</tt> is null and
326 >     * @throws NullPointerException if {@code fromElement} is null and
327       *         this set uses natural ordering, or its comparator does
328       *         not permit null elements
329       * @throws IllegalArgumentException {@inheritDoc}
330       * @since 1.6
331       */
332 <    public NavigableSet<E> navigableTailSet(E fromElement) {
333 <        return new TreeSet<E>(m.navigableTailMap(fromElement));
332 >    public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
333 >        return new TreeSet<E>(m.navigableTailMap(fromElement, inclusive));
334      }
335  
336      /**
326 –     * Equivalent to {@link #navigableSubSet} but with a return type
327 –     * conforming to the <tt>SortedSet</tt> interface.
328 –     *
329 –     * <p>{@inheritDoc}
330 –     *
337       * @throws ClassCastException {@inheritDoc}
338 <     * @throws NullPointerException if <tt>fromElement</tt> or
339 <     *         <tt>toElement</tt> is null and this set uses natural ordering,
338 >     * @throws NullPointerException if {@code fromElement} or
339 >     *         {@code toElement} is null and this set uses natural ordering,
340       *         or its comparator does not permit null elements
341       * @throws IllegalArgumentException {@inheritDoc}
342       */
343      public SortedSet<E> subSet(E fromElement, E toElement) {
344 <        return new TreeSet<E>(m.navigableSubMap(fromElement, toElement));
344 >        return navigableSubSet(fromElement, true, toElement, false);
345      }
346  
347      /**
342 –     * Equivalent to {@link #navigableHeadSet} but with a return type
343 –     * conforming to the <tt>SortedSet</tt> interface.
344 –     *
345 –     * <p>{@inheritDoc}
346 –     *
348       * @throws ClassCastException {@inheritDoc}
349 <     * @throws NullPointerException if <tt>toElement</tt> is null
349 >     * @throws NullPointerException if {@code toElement} is null
350       *         and this set uses natural ordering, or its comparator does
351       *         not permit null elements
352       * @throws IllegalArgumentException {@inheritDoc}
353       */
354      public SortedSet<E> headSet(E toElement) {
355 <        return new TreeSet<E>(m.navigableHeadMap(toElement));
355 >        return navigableHeadSet(toElement, false);
356      }
357  
358      /**
358 –     * Equivalent to {@link #navigableTailSet} but with a return type
359 –     * conforming to the <tt>SortedSet</tt> interface.
360 –     *
361 –     * <p>{@inheritDoc}
362 –     *
359       * @throws ClassCastException {@inheritDoc}
360 <     * @throws NullPointerException if <tt>fromElement</tt> is null
360 >     * @throws NullPointerException if {@code fromElement} is null
361       *         and this set uses natural ordering, or its comparator does
362       *         not permit null elements
363       * @throws IllegalArgumentException {@inheritDoc}
364       */
365      public SortedSet<E> tailSet(E fromElement) {
366 <        return new TreeSet<E>(m.navigableTailMap(fromElement));
366 >        return navigableTailSet(fromElement, true);
367      }
368  
369      public Comparator<? super E> comparator() {
# Line 451 | Line 447 | public class TreeSet<E>
447      }
448  
449      /**
450 <     * Returns a shallow copy of this <tt>TreeSet</tt> instance. (The elements
450 >     * Returns a shallow copy of this {@code TreeSet} instance. (The elements
451       * themselves are not cloned.)
452       *
453       * @return a shallow copy of this set
# Line 465 | Line 461 | public class TreeSet<E>
461          }
462  
463          clone.m = new TreeMap<E,Object>(m);
468 –
464          return clone;
465      }
466  
467      /**
468 <     * Save the state of the <tt>TreeSet</tt> instance to a stream (that is,
468 >     * Save the state of the {@code TreeSet} instance to a stream (that is,
469       * serialize it).
470       *
471       * @serialData Emits the comparator used to order this set, or
472 <     *             <tt>null</tt> if it obeys its elements' natural ordering
472 >     *             {@code null} if it obeys its elements' natural ordering
473       *             (Object), followed by the size of the set (the number of
474       *             elements it contains) (int), followed by all of its
475       *             elements (each an Object) in order (as determined by the
# Line 498 | Line 493 | public class TreeSet<E>
493      }
494  
495      /**
496 <     * Reconstitute the <tt>TreeSet</tt> instance from a stream (that is,
496 >     * Reconstitute the {@code TreeSet} instance from a stream (that is,
497       * deserialize it).
498       */
499      private void readObject(java.io.ObjectInputStream s)

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines