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}