Java Coder

  1 public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>,
  2         Cloneable, java.io.Serializable {
  3     /**
  4      * The backing map.
  5      */
  6     private transient NavigableMap<E, Object> m;
  7 
  8     // Dummy value to associate with an Object in the backing Map
  9     private static final Object PRESENT = new Object();
 10 
 11     // 非public的构造方法，被其它public构造方法调用
 12     TreeSet(NavigableMap<E, Object> m) {
 13         this.m = m;
 14     }
 15 
 16     /**
 17      * Constructs a new, empty tree set, sorted according to the natural
 18      * ordering of its elements. All elements inserted into the set must
 19      * implement the {@link Comparable} interface. Furthermore, all such
 20      * elements must be <i>mutually comparable</i>: {@code e1.compareTo(e2)}
 21      * must not throw a {@code ClassCastException} for any elements {@code e1}
 22      * and {@code e2} in the set. If the user attempts to add an element to the
 23      * set that violates this constraint (for example, the user attempts to add
 24      * a string element to a set whose elements are integers), the {@code add}
 25      * call will throw a {@code ClassCastException}.
 26      */
 27     public TreeSet() {
 28         this(new TreeMap<E, Object>());
 29     }
 30 
 31     /**
 32      * Constructs a new, empty tree set, sorted according to the specified
 33      * comparator. All elements inserted into the set must be <i>mutually
 34      * comparable</i> by the specified comparator: {@code comparator.compare(e1,
 35      * e2)} must not throw a {@code ClassCastException} for any elements {@code
 36      * e1} and {@code e2} in the set. If the user attempts to add an element to
 37      * the set that violates this constraint, the {@code add} call will throw a
 38      * {@code ClassCastException}.
 39      * 
 40      * @param comparator
 41      *            the comparator that will be used to order this set. If {@code
 42      *            null}, the {@linkplain Comparable natural ordering} of the
 43      *            elements will be used.
 44      */
 45     public TreeSet(Comparator<? super E> comparator) {
 46         this(new TreeMap<E, Object>(comparator));
 47     }
 48 
 49     /**
 50      * Constructs a new tree set containing the elements in the specified
 51      * collection, sorted according to the <i>natural ordering</i> of its
 52      * elements. All elements inserted into the set must implement the
 53      * {@link Comparable} interface. Furthermore, all such elements must be
 54      * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
 55      * {@code ClassCastException} for any elements {@code e1} and {@code e2} in
 56      * the set.
 57      * 
 58      * @param c
 59      *            collection whose elements will comprise the new set
 60      * @throws ClassCastException
 61      *             if the elements in {@code c} are not {@link Comparable}, or
 62      *             are not mutually comparable
 63      * @throws NullPointerException
 64      *             if the specified collection is null
 65      */
 66     public TreeSet(Collection<? extends E> c) {
 67         this();
 68         // 按照自然排序加入所有元素
 69         addAll(c);
 70     }
 71 
 72     /**
 73      * Constructs a new tree set containing the same elements and using the same
 74      * ordering as the specified sorted set.
 75      * 
 76      * @param s
 77      *            sorted set whose elements will comprise the new set
 78      * @throws NullPointerException
 79      *             if the specified sorted set is null
 80      */
 81     public TreeSet(SortedSet<E> s) {
 82         // 使用s的排序方法构造对象
 83         this(s.comparator());
 84         addAll(s);
 85     }
 86 
 87     /**
 88      * Returns an iterator over the elements in this set in ascending order.
 89      * 
 90      * @return an iterator over the elements in this set in ascending order
 91      */
 92     public Iterator<E> iterator() {
 93         // 按升序排列返回TreeMap的keys
 94         return m.navigableKeySet().iterator();
 95     }
 96 
 97     /**
 98      * Returns an iterator over the elements in this set in descending order.
 99      * 
100      * @return an iterator over the elements in this set in descending order
101      * @since 1.6
102      */
103     public Iterator<E> descendingIterator() {
104         // 按降序排列返回TreeMap的keys
105         return m.descendingKeySet().iterator();
106     }
107 
108     /**
109      * @since 1.6
110      */
111     public NavigableSet<E> descendingSet() {
112         return new TreeSet(m.descendingMap());
113     }
114 
115     /**
116      * Returns the number of elements in this set (its cardinality).
117      * 
118      * @return the number of elements in this set (its cardinality)
119      */
120     public int size() {
121         return m.size();
122     }
123 
124     /**
125      * Returns {@code true} if this set contains no elements.
126      * 
127      * @return {@code true} if this set contains no elements
128      */
129     public boolean isEmpty() {
130         return m.isEmpty();
131     }
132 
133     /**
134      * Returns {@code true} if this set contains the specified element. More
135      * formally, returns {@code true} if and only if this set contains an
136      * element {@code e} such that
137      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
138      * 
139      * @param o
140      *            object to be checked for containment in this set
141      * @return {@code true} if this set contains the specified element
142      * @throws ClassCastException
143      *             if the specified object cannot be compared with the elements
144      *             currently in the set
145      * @throws NullPointerException
146      *             if the specified element is null and this set uses natural
147      *             ordering, or its comparator does not permit null elements
148      */
149     public boolean contains(Object o) {
150         return m.containsKey(o);
151     }
152 
153     /**
154      * Adds the specified element to this set if it is not already present. More
155      * formally, adds the specified element {@code e} to this set if the set
156      * contains no element {@code e2} such that
157      * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>. If this
158      * set already contains the element, the call leaves the set unchanged and
159      * returns {@code false}.
160      * 
161      * @param e
162      *            element to be added to this set
163      * @return {@code true} if this set did not already contain the specified
164      *         element
165      * @throws ClassCastException
166      *             if the specified object cannot be compared with the elements
167      *             currently in this set
168      * @throws NullPointerException
169      *             if the specified element is null and this set uses natural
170      *             ordering, or its comparator does not permit null elements
171      */
172     public boolean add(E e) {
173         // 允许加入null元素
174         return m.put(e, PRESENT) == null;
175     }
176 
177     /**
178      * Removes the specified element from this set if it is present. More
179      * formally, removes an element {@code e} such that
180      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>, if this
181      * set contains such an element. Returns {@code true} if this set contained
182      * the element (or equivalently, if this set changed as a result of the
183      * call). (This set will not contain the element once the call returns.)
184      * 
185      * @param o
186      *            object to be removed from this set, if present
187      * @return {@code true} if this set contained the specified element
188      * @throws ClassCastException
189      *             if the specified object cannot be compared with the elements
190      *             currently in this set
191      * @throws NullPointerException
192      *             if the specified element is null and this set uses natural
193      *             ordering, or its comparator does not permit null elements
194      */
195     public boolean remove(Object o) {
196         return m.remove(o) == PRESENT;
197     }
198 
199     /**
200      * Removes all of the elements from this set. The set will be empty after
201      * this call returns.
202      */
203     public void clear() {
204         m.clear();
205     }
206 
207     /**
208      * Adds all of the elements in the specified collection to this set.
209      * 
210      * @param c
211      *            collection containing elements to be added to this set
212      * @return {@code true} if this set changed as a result of the call
213      * @throws ClassCastException
214      *             if the elements provided cannot be compared with the elements
215      *             currently in the set
216      * @throws NullPointerException
217      *             if the specified collection is null or if any element is null
218      *             and this set uses natural ordering, or its comparator does
219      *             not permit null elements
220      */
221     public boolean addAll(Collection<? extends E> c) {
222         // Use linear-time version if applicable
223         if (m.size() == 0 && c.size() > 0 && c instanceof SortedSet
224                 && m instanceof TreeMap) {
225             SortedSet<? extends E> set = (SortedSet<? extends E>) c;
226             TreeMap<E, Object> map = (TreeMap<E, Object>) m;
227             Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
228             Comparator<? super E> mc = map.comparator();
229             if (cc == mc || (cc != null && cc.equals(mc))) {
230                 // 需要研究addAllForTreeSet(set,obj)方法
231                 map.addAllForTreeSet(set, PRESENT);
232                 return true;
233             }
234         }
235         return super.addAll(c);
236     }
237 
238     /**
239      * @throws ClassCastException
240      *             {@inheritDoc}
241      * @throws NullPointerException
242      *             if {@code fromElement} or {@code toElement} is null and this
243      *             set uses natural ordering, or its comparator does not permit
244      *             null elements
245      * @throws IllegalArgumentException
246      *             {@inheritDoc}
247      * @since 1.6
248      */
249     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
250             E toElement, boolean toInclusive) {
251         return new TreeSet<E>(m.subMap(fromElement, fromInclusive, toElement,
252                 toInclusive));
253     }
254 
255     /**
256      * @throws ClassCastException
257      *             {@inheritDoc}
258      * @throws NullPointerException
259      *             if {@code toElement} is null and this set uses natural
260      *             ordering, or its comparator does not permit null elements
261      * @throws IllegalArgumentException
262      *             {@inheritDoc}
263      * @since 1.6
264      */
265     public NavigableSet<E> headSet(E toElement, boolean inclusive) {
266         return new TreeSet<E>(m.headMap(toElement, inclusive));
267     }
268 
269     /**
270      * @throws ClassCastException
271      *             {@inheritDoc}
272      * @throws NullPointerException
273      *             if {@code fromElement} is null and this set uses natural
274      *             ordering, or its comparator does not permit null elements
275      * @throws IllegalArgumentException
276      *             {@inheritDoc}
277      * @since 1.6
278      */
279     public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
280         return new TreeSet<E>(m.tailMap(fromElement, inclusive));
281     }
282 
283     /**
284      * @throws ClassCastException
285      *             {@inheritDoc}
286      * @throws NullPointerException
287      *             if {@code fromElement} or {@code toElement} is null and this
288      *             set uses natural ordering, or its comparator does not permit
289      *             null elements
290      * @throws IllegalArgumentException
291      *             {@inheritDoc}
292      */
293     public SortedSet<E> subSet(E fromElement, E toElement) {
294         return subSet(fromElement, true, toElement, false);
295     }
296 
297     /**
298      * @throws ClassCastException
299      *             {@inheritDoc}
300      * @throws NullPointerException
301      *             if {@code toElement} is null and this set uses natural
302      *             ordering, or its comparator does not permit null elements
303      * @throws IllegalArgumentException
304      *             {@inheritDoc}
305      */
306     public SortedSet<E> headSet(E toElement) {
307         return headSet(toElement, false);
308     }
309 
310     /**
311      * @throws ClassCastException
312      *             {@inheritDoc}
313      * @throws NullPointerException
314      *             if {@code fromElement} is null and this set uses natural
315      *             ordering, or its comparator does not permit null elements
316      * @throws IllegalArgumentException
317      *             {@inheritDoc}
318      */
319     public SortedSet<E> tailSet(E fromElement) {
320         return tailSet(fromElement, true);
321     }
322 
323     public Comparator<? super E> comparator() {
324         // 如果使用自然排序，返回null
325         return m.comparator();
326     }
327 
328     /**
329      * @throws NoSuchElementException
330      *             {@inheritDoc}
331      */
332     public E first() {
333         return m.firstKey();
334     }
335 
336     /**
337      * @throws NoSuchElementException
338      *             {@inheritDoc}
339      */
340     public E last() {
341         return m.lastKey();
342     }
343 
344     // NavigableSet API methods
345 
346     /**
347      * @throws ClassCastException
348      *             {@inheritDoc}
349      * @throws NullPointerException
350      *             if the specified element is null and this set uses natural
351      *             ordering, or its comparator does not permit null elements
352      * @since 1.6
353      */
354     public E lower(E e) {
355         // 小于它的元素，没有则返回null
356         return m.lowerKey(e);
357     }
358 
359     /**
360      * @throws ClassCastException
361      *             {@inheritDoc}
362      * @throws NullPointerException
363      *             if the specified element is null and this set uses natural
364      *             ordering, or its comparator does not permit null elements
365      * @since 1.6
366      */
367     public E floor(E e) {
368         // 小于等于它的元素，没有则返回null
369         return m.floorKey(e);
370     }
371 
372     /**
373      * @throws ClassCastException
374      *             {@inheritDoc}
375      * @throws NullPointerException
376      *             if the specified element is null and this set uses natural
377      *             ordering, or its comparator does not permit null elements
378      * @since 1.6
379      */
380     public E ceiling(E e) {
381         // 大于等于它的元素，没有则返回null
382         return m.ceilingKey(e);
383     }
384 
385     /**
386      * @throws ClassCastException
387      *             {@inheritDoc}
388      * @throws NullPointerException
389      *             if the specified element is null and this set uses natural
390      *             ordering, or its comparator does not permit null elements
391      * @since 1.6
392      */
393     public E higher(E e) {
394         // 大于它的元素，没有则返回null
395         return m.higherKey(e);
396     }
397 
398     /**
399      * @since 1.6
400      */
401     public E pollFirst() {
402         // 弹出第一个元素并删除
403         Map.Entry<E, ?> e = m.pollFirstEntry();
404         return (e == null) ? null : e.getKey();
405     }
406 
407     /**
408      * @since 1.6
409      */
410     public E pollLast() {
411         // 弹出最后一个元素并删除
412         Map.Entry<E, ?> e = m.pollLastEntry();
413         return (e == null) ? null : e.getKey();
414     }
415 
416     /**
417      * Returns a shallow copy of this {@code TreeSet} instance. (The elements
418      * themselves are not cloned.)
419      * 
420      * @return a shallow copy of this set
421      */
422     public Object clone() {
423         TreeSet<E> clone = null;
424         try {
425             clone = (TreeSet<E>) super.clone();
426         } catch (CloneNotSupportedException e) {
427             throw new InternalError();
428         }
429 
430         // 元素引用的赋值，浅层拷贝
431         clone.m = new TreeMap<E, Object>(m);
432         return clone;
433     }
434 
435     /**
436      * Save the state of the {@code TreeSet} instance to a stream (that is,
437      * serialize it).
438      * 
439      * @serialData Emits the comparator used to order this set, or {@code null}
440      *             if it obeys its elements' natural ordering (Object), followed
441      *             by the size of the set (the number of elements it contains)
442      *             (int), followed by all of its elements (each an Object) in
443      *             order (as determined by the set's Comparator, or by the
444      *             elements' natural ordering if the set has no Comparator).
445      */
446     private void writeObject(java.io.ObjectOutputStream s)
447             throws java.io.IOException {
448         // Write out any hidden stuff
449         s.defaultWriteObject();
450 
451         // Write out Comparator
452         s.writeObject(m.comparator());
453 
454         // Write out size
455         s.writeInt(m.size());
456 
457         // Write out all elements in the proper order.
458         for (Iterator i = m.keySet().iterator(); i.hasNext();)
459             s.writeObject(i.next());
460     }
461 
462     /**
463      * Reconstitute the {@code TreeSet} instance from a stream (that is,
464      * deserialize it).
465      */
466     private void readObject(java.io.ObjectInputStream s)
467             throws java.io.IOException, ClassNotFoundException {
468         // Read in any hidden stuff
469         s.defaultReadObject();
470 
471         // Read in Comparator
472         Comparator<? super E> c = (Comparator<? super E>) s.readObject();
473 
474         // Create backing TreeMap
475         TreeMap<E, Object> tm;
476         if (c == null)
477             tm = new TreeMap<E, Object>();
478         else
479             tm = new TreeMap<E, Object>(c);
480         m = tm;
481 
482         // Read in size
483         int size = s.readInt();
484 
485         // 对输入流对象继续还原对象
486         tm.readTreeSet(size, s, PRESENT);
487     }
488 
489     private static final long serialVersionUID = -2479143000061671589L;
490 }
491