001 /* TreeSet.java -- a class providing a TreeMap-backed SortedSet
002 Copyright (C) 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038
039 package java.util;
040
041 import java.io.IOException;
042 import java.io.ObjectInputStream;
043 import java.io.ObjectOutputStream;
044 import 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 */
084 public 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 }